On the integrality of an extreme solution to pluperfect graph and balanced systems

Let A be a nonnegative integer matrix, and let e denote the vector all of whose components are equal to 1. The pluperfect graph theorem states that if for all integer vectors b the optimal objective value of the linear program minse′xvbAx ? b, x ? 0 s is integer, then those linear programs possess optimal integer solutions. We strengthen this theorem and show that any lexicomaximal optimal solution to the above linear program (under any arbitrary ordering of the variables) is integral and an extreme point of sxvbAx ? b, x ? 0 s. We note that this extremality property of integer solutions is also shared by covering as well as packing problems defined by a balanced matrix A.     

Properties of submatrices of Sylvester Hadamard matrices

We investigate the algebraic behaviour of leading principal submatrices of Hadamard matrices being powers of 2. We provide analytically the spectrum of general submatrices of these Hadamard matrices. Symmetry properties and relationships between the upper left and lower right corners of the matrices in this respect are demonstrated. Considering the specific construction scheme of this particular class of Hadamard matrices (called Sylvester Hadamard matrices), we utilize tensor operations to prove the respective results. An algorithmic procedure yielding the complete spectrum of leading principal submatrices of Sylvester Hadamard matrices is proposed.     

Norms and perfect graphs

The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods.In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.This is a written account of an invited lecture delivered by the second author on occasion of the 12. Symposium on Operations Research, Passau, 9.–11. 9. 1987.     

Inversion of conjugate-Toeplitz matrices and conjugate-Hankel matrices

The inverses of conjugate-Toeplitz (CT) and conjugate-Hankel (CH) matrices can be expressed by the Gohberg–Heinig type formula. We obtain an explicit inverse formula of CT matrix. Similarly, the formula and the decomposition of the inverse of a CH matrix are provided. Also the stability of the inverse formulas of CT and CH matrices are discussed. Examples are provided to verify the feasibility of the algorithms.     

Direct sums of balanced functions,perfect nonlinear functions,and orthogonal cocycles

Determining if a direct sum of functions inherits nonlinearity properties from its direct summands is a subtle problem. Here, we correct a statement by Nyberg on inheritance of balance and we use a connection between balanced derivatives and orthogonal cocycles to generalize Nyberg's result to orthogonal cocycles. We obtain a new search criterion for PN functions and orthogonal cocycles mapping to non‐cyclic abelian groups and use it to find all the orthogonal cocycles over Z ₂^t, 2 ≤ t ≤ 4. We conjecture that any orthogonal cocycle over Z ₂^t, t ≥ 2, must be multiplicative. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 173–181, 2008     

Double perfect partitions

MacMahon [Combinatory Analysis, vols. I and II, Cambridge University Press, Cambridge, 1915, 1916 (reprinted, Chelsea, 1960)] introduced a perfect partition of positive integer n, which is a partition such that every positive integer less than or equal to n can be uniquely represented by the sum of its parts. We generalize perfect partition and find a relation with ordered factorizations.     

On perfect Lee codes

In this paper we survey recent results on the Golomb-Welch conjecture and its generalizations and variations. We also show that there are no perfect 2-error correcting Lee codes of block length 5 and 6 over Z. This provides additional support for the Golomb Welch conjecture as it settles the two smallest cases open so far.     

Completely normal matrices

Normal matrices in which all submatrices are normal are said to be completely normal. We characterize this class of matrices, determine the possible inertias of a particular completely normal matrix, and show that real matrices in this class are closed under (general) Schur complementation. We provide explicit formulas for the Moore–Penrose inverse of a completely normal matrix of size at least four. A result on irreducible principally normal matrices is derived as well.     

The non-existence of some perfect codes over non-prime power alphabets

Let denote the number of times the prime number p appears in the prime factorization of the integer q. The following result is proved: If there is a perfect 1-error correcting code of length n over an alphabet with q symbols then, for every prime number .This condition is stronger than both the packing condition and the necessary condition given by the Lloyd theorem, as it for example excludes the existence of a perfect code with the parameters (n,q,e)=(19,6,1).     

Approximation of high-dimensional kernel matrices by multilevel circulant matrices

Kernels are important in developing a variety of numerical methods, such as approximation, interpolation, neural networks, machine learning and meshless methods for solving engineering problems. A common problem of these kernel-based methods is to calculate inverses of kernel matrices generated by a kernel function and a set of points. Due to the denseness of these matrices, finding their inverses is computationally costly. To overcome this difficulty, we introduce in this paper an approximation of the kernel matrices by appropriate multilevel circulant matrices so that the fast Fourier transform can be applied to reduce the computational cost. Convergence analysis for the proposed approximation is established based on certain decay properties of the kernels.     

On kernels of perfect codes

It is shown that there exists a perfect one-error-correcting binary code with a kernel which is not contained in any Hamming code.     

Near-perfect matrices

A 0, 1 matrixA isnear-perfect if the integer hull of the polyhedron {x0: Ax } can be obtained by adding one extra (rank) constraint. We show that in general, such matrices arise as the cliquenode incidence matrices of graphs. We give a colouring-like characterization of the corresponding class of near-perfect graphs which shows that one need only check integrality of a certain linear program for each 0, 1, 2-valued objective function. This in contrast with perfect matrices where it is sufficient to check 0, 1-valued objective functions. We also make the following conjecture: a graph is near-perfect if and only if sequentially lifting any rank inequality associated with a minimally imperfect graph results in the rank inequality for the whole graph. We show that the conjecture is implied by the Strong Perfect Graph Conjecture. (It is also shown to hold for graphs with no stable set of size eleven.) Our results are used to strengthen (and give a new proof of) a theorem of Padberg. This results in a new characterization of minimally imperfect graphs: a graph is minimally imperfect if and only if both the graph and its complement are near-perfect.The research has partially been done when the author visited Mathematic Centrum, CWI, Amsterdam, The Netherlands.     

Elementary matrices and products of idempotents

We study the relations between product decomposition of singular matrices into products of idempotent matrices and product decomposition of invertible matrices into elementary ones.     

Enumerating and decoding perfect linear Lee codes

Using group theory approach, we determine all numbers q for which there exists a linear 1-error correcting perfect Lee code of block length n over Z _q , and then we enumerate those codes. At the same time this approach allows us to design a linear time decoding algorithm.      

On perfect simple-injective rings

Harada calls a ring right simple-injective if every -homomorphism with simple image from a right ideal of to is given by left multiplication by an element of . In this paper we show that every left perfect, left and right simple-injective ring is quasi-Frobenius, extending a well known result of Osofsky on self-injective rings. It is also shown that if is left perfect and right simple-injective, then is quasi-Frobenius if and only if the second socle of is countably generated as a left -module, extending many recent results on self-injective rings. Examples are given to show that our results are non-trivial extensions of those on self-injective rings.

     

On diameter perfect constant-weight ternary codes

From cosets of binary Hamming codes we construct diameter perfect constant-weight ternary codes with weight n-1 (where n is the code length) and distances 3 and 5. The class of distance 5 codes has parameters unknown before.     

On the complexity of SNP block partitioning under the perfect phylogeny model

Recent technologies for typing single nucleotide polymorphisms (SNPs) across a population are producing genome-wide genotype data for tens of thousands of SNP sites. The emergence of such large data sets underscores the importance of algorithms for large-scale haplotyping. Common haplotyping approaches first partition the SNPs into blocks of high linkage-disequilibrium, and then infer haplotypes for each block separately. We investigate an integrated haplotyping approach where a partition of the SNPs into a minimum number of non-contiguous subsets is sought, such that each subset can be haplotyped under the perfect phylogeny model. We show that finding an optimum partition is -hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.     

Parametrization of balanced multiwavelet

This paper deals with the parametrization of balanced multiwavelets and different properties associated with them. We introduce the property balancing symmetry and orthogonal properties of multiwavelet and link these properties to the matrix of the low pass synthesis multifilter. Using these new results, we present the parametrization of orthogonal multiwavelets of flip-symmetry with length two and three. This is a direct construction method, making the construction of the balanced multiwavelet as easy as the scalar wavelet.     

Maximal partial packings of $${Z_2^n}$$ with perfect codes

A maximal partial Hamming packing of is a family of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in . The number of translates of Hamming codes in is the packing number, and a partial Hamming packing is strictly partial if the family does not constitute a partition of . A simple and useful condition describing when two translates of Hamming codes are disjoint or not disjoint is proved. This condition depends on the dual codes of the corresponding Hamming codes. Partly, by using this condition, it is shown that the packing number p, for any maximal strictly partial Hamming packing of , n = 2 ^m −1, satisfies . It is also proved that for any n equal to 2 ^m −1, , there exist maximal strictly partial Hamming packings of with packing numbers n−10,n−9,n−8,...,n−1. This implies that the upper bound is tight for any n = 2 ^m −1, . All packing numbers for maximal strictly partial Hamming packings of , n = 7 and 15, are found by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5,6,7,...,13 and 14.