Generalized weighing matrices and self-orthogonal codes

It is shown that the row spaces of certain generalized weighing matrices, Bhaskar Rao designs, and generalized Hadamard matrices over a finite field of order q are hermitian self-orthogonal codes. Certain matrices of minimum rank yield optimal codes. In the special case when q=4, the codes are linked to quantum error-correcting codes, including some codes with optimal parameters.     

Some Combinatorial Aspects of Constructing Bipartite-Graph Codes

We propose geometrical methods for constructing square 01-matrices with the same number n of units in every row and column, and such that any two rows of the matrix contain at most one unit in common. These matrices are equivalent to n-regular bipartite graphs without 4-cycles, and therefore can be used for the construction of efficient bipartite-graph codes such that both the classes of its vertices are associated with local constraints. We significantly extend the region of parameters m, n for which there exist an n-regular bipartite graph with 2m vertices and without 4-cycles. In that way we essentially increase the region of lengths and rates of the corresponding bipartite-graph codes. Many new matrices are either circulant or consist of circulant submatrices: this provides code parity-check matrices consisting of circulant submatrices, and hence quasi-cyclic bipartite-graph codes with simple implementation.     

Transportation matrices with staircase patterns and majorization

We consider some questions concerning transportation matrices with a certain nonzero pattern. For a given staircase pattern we characterize those row sum vectors R and column sum vectors S such that the corresponding class of transportation matrices with the given row and column sums and the given pattern is nonempty. Two versions of this problem are considered. Algorithms for finding matrices in these matrix classes are introduced and, finally, a connection to the notion of majorization is discussed.     

The Existence and Application of Strongly Idempotent Self-orthogonal Row Latin Magic Arrays

Let N = {0, 1, · · ·, n ? 1}. A strongly idempotent self-orthogonal row Latin magic array of order n (SISORLMA(n) for short) based on N is an n × n array M satisfying the following properties: (1) each row of M is a permutation of N, and at least one column is not a permutation of N; (2) the sums of the n numbers in every row and every column are the same; (3) M is orthogonal to its transpose; (4) the main diagonal and the back diagonal of M are 0, 1, · · ·, n ? 1 from left to right. In this paper, it is proved that an SISORLMA(n) exists if and only if n ? {2, 3}. As an application, it is proved that a nonelementary rational diagonally ordered magic square exists if and only if n ? {2, 3}, and a rational diagonally ordered magic square exists if and only if n ≠ 2.     

Matrices with different Gondran–Minoux and determinantal ranks over max-algebras

Let GMr(A) be the row Gondran–Minoux rank of a matrix, GMc(A) be the column Gondran–Minoux rank, and d(A) be the determinantal rank, respectively. The following problem was posed by M. Akian, S. Gaubert, and A. Guterman: Find the minimal numbers m and n such that there exists an (m × n)-matrix B with different row and column Gondran–Minoux ranks. We prove that in the case GMr(B) > GMc(B) the minimal m and n are equal to 5 and 6, respectively, and in the case GMc(B) > GMr(B) the numbers m = 6 and n = 5 are minimal. An example of a matrix $ A \in {\mathcal{M}_{5 \times 6}}\left( {{\mathbb{R}_{\max }}} \right) $ such that GMr(A) = GMc(A ^t) = 5 and GMc(A) = GMr(A ^t) = 4 is provided. It is proved that p = 5 and q = 6 are the minimal numbers such that there exists an (p×q)-matrix with different row Gondran–Minoux and determinantal ranks.     

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

Properties of (0, 1)-matrices without certain configurations

We generalize results of Ryser on (0, 1)-matrices without triangles, 3 × 3 submatrices with row and column sums 2. The extremal case of matrices without triangles was previously studied by the author. Let the row intersection of row i and row j (i ≠ j) of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do not 0 otherwise. For matrices satisfying some conditions on forbidden configurations and column sums ? 2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. The extremal matrices with m rows and $\text{(}\text{m}\text{2}\text{)}$ distinct columns have a unique SDR of pairs of rows with 1's. A triangle bordered with a column of 0's and its (0, 1)-complement are also considered as forbidden configurations. Similar results are obtained and the extremal matrices are closely related to the extremal matrices without triangles.     

A generalization of the Nash equilibrium theorem on bimatrix games

In this article, we consider a two-person game in which the first player picks a row representative matrixM from a nonempty set $A$ ofm ×n matrices and a probability distributionx on {1,2,...,m} while the second player picks a column representative matrixN from a nonempty set ? ofm ×n matrices and a probability distribution y on 1,2,...,n. This leads to the respective costs ofx ^t My andx ^t Ny for these players. We establish the existence of an ?-equilibrium for this game under the assumption that $A$ and ? are bounded. When the sets $A$ and ? are compact in ?^mxn, the result yields an equilibrium state at which stage no player can decrease his cost by unilaterally changing his row/column selection and probability distribution. The result, when further specialized to singleton sets, reduces to the famous theorem of Nash on bimatrix games.     

A combinatorial problem associated with nonograms

Associated with an m × n matrix with entries 0 or 1 are the m-vector of row sums and n-vector of column sums. In this article we study the set of all pairs of these row and column sums for fixed m and n. In particular, we give an algorithm for finding all such pairs for a given m and n.     

Evaluation of the Hamming weights of a class of linear codes based on Gauss sums

Linear codes with a few weights have been widely investigated in recent years. In this paper, we mainly use Gauss sums to represent the Hamming weights of a class of q-ary linear codes under some certain conditions, where q is a power of a prime. The lower bound of its minimum Hamming distance is obtained. In some special cases, we evaluate the weight distributions of the linear codes by semi-primitive Gauss sums and obtain some one-weight, two-weight linear codes. It is quite interesting that we find new optimal codes achieving some bounds on linear codes. The linear codes in this paper can be used in secret sharing schemes, authentication codes and data storage systems.     

Properties of (0, 1)-matrices with no triangles

We study (0, 1)-matrices which contain no triangles (submatrices of order 3 with row and column sums 2) previously studied by Ryser. Let the row intersection of row i and row j of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do and a zero otherwise. For matrices with no triangles, columns sums ?2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. We then study the extremal (0, 1)-matrices with no triangles, column sums ?2, distinct columns, i.e., those of size mx(^m₂). The number of columns of column sum l is m ? l + 1 and they form a (l ? 1)-tree. The ((^m₂)) columns have a unique SDR of pairs of rows with 1's. Also, these matrices have a fascinating inductive buildup. We finish with an algorithm for constructing these matrices.     

The automorphism groups of Reed-Solomon codes

A class of maximum distance separable codes is introduced which includes Reed Solomon codes; extended Reed-Solomon codes, and other cyclic or pseudocyclie MDS codes studied recently. This class of codes, which we call “Cauchy codes” because of the special form of their generator matrices, forms a closed submanifold of dimension 2n - 4 in the k × (n - k)-dimensional algebraic manifold of all MDS codes of length n and dimension k. For every Cauchy code we determine the automorphism group and its underlying permutation group. Far doubly-extended Reed-Solomon codes over GF(q) the permutation group is the semilinear fractional group PΛL(2, q).     

Euclidean and Hermitian LCD MDS codes

Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. On the other hand, being optimal codes, maximum distance separable codes (abbreviated MDS) are of much interest from many viewpoints due to their theoretical and practical properties. However, little work has been done on LCD MDS codes. In particular, determining the existence of q-ary [n, k] LCD MDS codes for various lengths n and dimensions k is a basic and interesting problem. In this paper, we firstly study the problem of the existence of q-ary [n, k] LCD MDS codes and solve it for the Euclidean case. More specifically, we show that for \(q>3\) there exists a q-ary [n, k] Euclidean LCD MDS code, where \(0\le k \le n\le q+1\), or, \(q=2^{m}\), \(n=q+2\) and \(k= 3 \text { or } q-1\). Secondly, we investigate several constructions of new Euclidean and Hermitian LCD MDS codes. Our main techniques in constructing Euclidean and Hermitian LCD MDS codes use some linear codes with small dimension or codimension, self-orthogonal codes and generalized Reed-Solomon codes.     

The existence of (2 × c, λ) grid-block designs with {c\in \{3, 4, 5\}} and λ ≥ 1

Let X be a v-set and ${\mathcal{B}}$ a collection of r × c arrays with elements in X. Two elements of X are collinear if they are on the same grid line (row or column). A pair ${(X, \mathcal{B})}$ is called an (r × c, λ) grid-block design if every two distinct elements in X are collinear exactly λ times in the arrays of ${\mathcal{B}}$ . This design has absorbed much attention due to its use in DNA library screening. In this paper, we prove that the necessary conditions for the existence of (2 × c, λ) grid-block designs of order v with ${c\in \{3, 4, 5\}}$ and any integer λ ≥ 1 are also sufficient.     

The class A(R,S) of (0, 1)-matrices

Let R and S be two vectors whose components are m and n non-negative integers, respectively. Let $\text{A}$(R, S) be the class consisting of all (0, 1)-matrices of size m by n with row sum vector R and column sum vector S. In this paper we derive a lower bound to the cardinality of the class $\text{A}$(R, S), which can be computed readily.     

A doubly divisible nearly Kirkman system

In this note we exhibit an example of a new class of combinatorial array. A Room square [9] is an r × r square each of whose cells is either empty or contains a distinct unordered pair with entries from the set of integers {1, 2,…, r + 1} such that each integer appears exactly once in each row and exactly once in each column. We present an analogous square whose entries are unordered triples, none of whose two-element subsets is repeated.     

Constructions of projective linear codes by the intersection and difference of sets

Projective linear codes are a special class of linear codes whose dual codes have minimum distance at least 3. Projective linear codes with only a few weights are useful in authentication codes, secret sharing schemes, data storage systems and so on. In this paper, two constructions of q-ary linear codes are presented with defining sets given by the intersection and difference of two sets. These constructions produce several families of new projective two-weight or three-weight linear codes. As applications, our projective codes can be used to construct secret sharing schemes with interesting access structures, strongly regular graphs and association schemes with three classes.     

Generalized marginal homogeneity model and its relation to marginal equimoments for square contingency tables with ordered categories

For square contingency tables with ordered categories, Tomizawa (Calcutta Stat Assoc Bull 43:123–125, 1993a; Sankhyā Ser B 60:293–300, 1998) gave theorems that the marginal homogeneity (MH) model is equivalent to certain two or three models holding simultaneously. This paper proposes a generalized MH model, which describes a structure of the odds that an observation will fall in row category i or below and column category i + 1 or above, instead of in column category i or below and row category i + 1 or above. In addition, this paper gives the theorems that the MH model is equivalent to the generalized MH model and some models holding simultaneously whose each indicates: (1) the equality of m-order moment of row and column variables, (2) the equality of skewness of them and (3) the equality of kurtosis of them. When the MH model fits the data poorly, these may be useful for seeing the reason for the poor fit; for instance, the poor fit of the MH model is caused by the poor fit of the equality of row and column means rather than the generalized MH model. Examples are given.     

Room squares with super-simple property

Constant-composition codes are a special type of constant-weight codes and have attracted recent interest due to their numerous applications. In a recent work, the authors found that an optimal (n, 5, [2, 1, 1])₄-code of constant-composition can be obtained from a Room square of side n with super-simple property. In this paper, we study the existence problem of super-simple Room squares. The problem is solved leaving only two minimal possible n undetermined.