0
$\begingroup$

Let $M$ be a $n \times n$ matrix over the finite field of two elements that satisfies the following property$\colon$ the total number of 1's in each row coincides with one in each column. In other words, there is a number $N$ such that

  1. The number of non-zero elements in each row of $M$ is $N$.

  2. The number of non-zero elements in each column of $M$ is $N$.

Moreover, the matrix $M$ is such that the sum of some two distinct rows of $M$ is a row of $M$ also.

I hope there are non-trivial answers to the following questions.

Question 1. Which additional properties the matrix $M$ may has?

Question 2. Let $C$ be the binary code obtained as the right kernel of $M$. What can one say about the weight enumerator of $C$? In particular, what are the best bounds on the minimum distance of the code $C$ can be obtained?

I believe that, for example, the algebraic graph theory can be applied to the last question. Unfortunately, I am not a specialist in this theory (as well as in error-correcting codes).

More precisely, the rank of $M$ is less or equal to $q-1$ and $n=\frac{q^2-q}{2}$, $N=\frac{q^2-1}{4}$ where $q$ is an odd prime power.

UPD 1. For example, if $q=5$, then we obtain the following matrix$\colon$

$\left(\begin{array}{rrrrrrrrrr} 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \end{array}\right)$

$\endgroup$
  • $\begingroup$ If by sum of two rows you mean coordinatewise addition mod 2, then you have a 0-1 matrix of order m which is derived from a Hadamard matrix of order m+1. This is because the constant row sums plus the sum of rows condition imply orthogonal rows in the associated Hadamard matrix. Gerhard "Columns Properties Come For Free" Paseman, 2017.01.23. $\endgroup$ – Gerhard Paseman Jan 24 '17 at 2:01
  • $\begingroup$ I take it "sum of any two rows" means "sum of any two distinct rows". $\endgroup$ – Gerry Myerson Jan 24 '17 at 22:38
  • $\begingroup$ @GerryMyerson Yes, I corrected it. $\endgroup$ – Ivan Pogildiakov Jan 24 '17 at 23:25
  • $\begingroup$ @GerhardPaseman Your idea is not clear for me, since the size of a Hadamard matrix can not be equal to an arbitrary number. I added an example. Could you provide a Hadamard matrix for it, please? $\endgroup$ – Ivan Pogildiakov Jan 25 '17 at 1:44
  • 1
    $\begingroup$ Your example does not fit your conditions. The (mod 2) sum of the fourth and fifth row does not have 6 ones, therefore cannot be a row of the matrix. If you provide an example for q=5 which happens to have n=11 and N=6, and has the row sum property you mentioned, I will show you the Hadamard matrix derived from it. Gerhard "With Agreement On Row Sum" Paseman, 2017.01.24. $\endgroup$ – Gerhard Paseman Jan 25 '17 at 2:14
0
$\begingroup$

Unfortunately, the nice property that every distinct pair of rows yields another row by mod 2 vector addition has been withdrawn. However, it may be possible to regard M as having maximal subsets of rows where this property holds, and still say something useful about M.

The comment above regarding Hadamard matrices goes as follows: since every row has the same number N of ones, and since the sum of two rows A and B is also a row, the number N of ones is even, and the number of columns which have ones in both A and B is N/2, half the number of columns which have ones in either row A or row B.

Suppose we have a small collection F of rows of M that generates by mod 2 addition a slightly larger collection of rows G, such that G is a subset of rows of M, and such that the sum of any two rows of G also has N ones (even though the result may be not a row of M and thus outside of G). Suppose further we can adjust the length of the rows of G so that each row has as many zeros as it has ones, without giving up any of the ones already present in G.

Now, copy each row in G into a new set H, but for every zero replace it by -1, and let each row in H have N ones and the same number of occurrences of -1, by resizing if needed. Now every two distinct rows have dot product 0, and are part of a Hadamard matrix. If the closure property had held for M, the rows of H would be one coordinate longer, and with the addition of a row of all ones, would have formed a Hadamard matrix.

This suggests that the actual M is composed of fragments of a Hadamard matrix, somehow shortened and glued together. Since we do not know how large F or G is, it becomes challenging to say much more. However, if the matrix (Edit M when considered over the real numbers and not over the two element field, thank you Gerry Myerson) is of full rank (contrary to claims in the post), it may be possible to say something about the size of the determinant of M.

Gerhard "Imagines A Spectrum Of Possibilities" Paseman, 2017.01.24.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If there is even one pair of distinct rows whose sum is another row, then the matrix is not of full rank, right? $\endgroup$ – Gerry Myerson Jan 25 '17 at 5:21
  • 1
    $\begingroup$ I was unclear. In the above, I am working over the reals when I mention rank. Over the two element field, you are right, the matrix cannot be of full rank if it has three such rows, one the mod 2 sum of two others. Gerhard "Two Is Like Infinity, Right?" Paseman, 2017.01.24. $\endgroup$ – Gerhard Paseman Jan 25 '17 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.