# binary matrix and product between a matrix and its transpose

Let be $$A$$ a square matrix of order $$n$$ which has only the numbers $$0$$ and $$1$$ as entries such that: $$A+A^{T}+I_n=EE^{T}$$ where $$E=(1,1,...,1)^{T}$$

Find $$n$$ for which there is a matrix $$A$$ such that $$AA^{T}$$ has no null entries.

Let be $$a_{ij}$$ the entry of A on the line $$i$$ and column $$j$$, for every $$i,j\in \{1,2,...,n\}$$.

I have got that all entries on the first diagonal must be $$0$$. And if $$a_{ij}=1$$ then $$a_{ij}=0$$ and vice versa, where $$i\ne j$$ and $$i,j\in \{1,2,...,n\}$$ since we have $$A+A^{T}+I_n=EE^{T}$$ The relation $$A+A^{T}+I_n=EE^{T}$$ may be re-written equivalently as: $$A+A^{T}=\begin{pmatrix}0&1&1&...&1\\ 1&0&1&...&1\\ 1&1&0&...&1\\ ...&...&...&...&...\\ 1&1&1&...&0\end{pmatrix}$$

Can somebody give some examples for some particular cases? Maybe you can write a program to do it for you using backtracking for example. Maybe we can generalize it for every $$n\ge n_0$$.

I noticed that $$n\ge 6$$(I made a program :)) but it is inefficient for numbers greater than 6). So we know that $$A+A^{T}=\begin{pmatrix}0&1&1&...&1\\ 1&0&1&...&1\\ 1&1&0&...&1\\ ...&...&...&...&...\\ 1&1&1&...&0\end{pmatrix}$$ and $$AA^T=\begin{pmatrix}b_{11}&b_{12}&b_{13}&...&b_{1n}\\ b_{21}&b_{22}&b_{23}&...&b_{2n}\\ b_{31}&b_{31}&b_{33}&...&b_{3n}\\ ...&...&...&...&...\\ b_{n1}&b_{n2}&b_{n3}&...&b_{nn}\end{pmatrix}$$ where $$b_{ij}\ne 0\ , \text{for every } i,j\in \{1,2,...,n\}$$

## What do you think of case $$n=6$$? How can you prove that there are no matices with these properties without checking every possibility?

• Comments are not for extended discussion; this conversation has been moved to chat. Aug 17, 2021 at 23:39

There's a simple way to enumerate all such matrices for a fixed $$n$$. For a bit $$b$$ let $$\bar{b} = b + 1 \mod 2$$. Then for example for $$n=4$$ we have our matrix $$A$$ can be specified by a bitstring $$b_1b_2b_3b_4$$ in the following way: $$A = \begin{pmatrix} 0 & b_1 & b_2 & b_3 \\ \bar{b}_1 & 0 & b_4 & b_5 \\ \bar{b}_2 & \bar{b}_4 & 0 & b_6 \\ \bar{b}_3 & \bar{b}_5 & \bar{b}_6 & 0 \end{pmatrix}.$$ For a general $$n$$ we need a bitstring that can fill in the strictly upper triangular part of the matrix $$A$$. In particular, such a bit string is of length $$\frac{(n-1) n}{2}$$. Thus for $$n=6$$ there are $$2^{15}\approx 32000$$ binary matrices to check and for $$n=7$$ there are $$2^{21} \approx 2\,000\,000$$ which can be easily check by a modern computer.

Case: $$n=6$$

Numerically, one can exhaustively check all possibilities and we find no examples that solve the problem

Case: $$n=7$$

For $$n=7$$ there are many solutions to the problem and one in particular corresponds to the bitstring (using the encoding above) $$000111010010010100010$$ and therefore to the matrix $$\begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \end{pmatrix}\,.$$ You can check that $$AA^T$$ would evaluate to a matrix where all offdiagonal elements are $$1$$ and all diagonal elements are $$3$$.

CLAIM: For every $$n\geq 7$$, we can find $$A_{n\times n}$$ satisfying the required conditions.

Proof. It is an induction on $$n$$. The case $$n=7$$ was provided by Rammus.

Suppose there is $$A_{n\times n}$$ satisfying the required conditions. Let us build $$B_{n+1\times n+1}$$ satisfying the same conditions.

Let $$L_1$$ be the first row of $$A$$. Define $$x=(x_1,\ldots,x_n)=(1,1,\ldots,1)-L_1$$.

Let $$B=\begin{pmatrix} A & x^t\\ L_1 & 0 \end{pmatrix}$$.

Note that

1. $$(BB^t)_{ij}\geq (AA^t)_{ij}>0$$, for $$1\leq i,j\leq n$$,
2. $$(BB^t)_{(n+1)j}\geq (AA^t)_{1j}>0$$, for $$1\leq j\leq n$$, and
3. $$(BB^t)_{(n+1)(n+1)}= (AA^t)_{11}>0$$.

In addition, $$B+B^t+Id_{n+1\times n+1}=\begin{pmatrix} A+A^t+Id_{n\times n} & x^t+L_1^t\\ L_1+x & 1 \end{pmatrix}=1_{n+1\times n+1}$$.

The induction is complete. $$\square$$

The case $$n=6$$ does not work because each row must contain at least three 1s. See the claim below.

So $$\#\{(i,j),\ A_{ij}=1\}\geq 3n$$. By the required conditions $$\#\{(i,j),\ A_{ij}=1\}=\frac{n(n-1)}{2}$$. So $$\frac{n(n-1)}{2}\geq 3n$$, which implies $$n\geq 7$$.

CLAIM 2: If $$n\geq 3$$ then the number of 1s on each row of $$A$$ is at least 3.

Proof. If the row $$i$$ of $$A$$ contains only one number $$1$$, let us say $$A_{ij}=1$$, then row $$i$$ and row $$j$$ of $$A$$ are orthogonal, because $$A_{jj}=0$$. This is impossible, since $$AA^t_{ij}>0$$.

Next, let us assume that the row $$i$$ of $$A$$ contains only two numbers 1: $$A_{ij}=1$$ and $$A_{ik}=1$$. Of course, $$i$$, $$j$$ and $$k$$ are distinct.

Since $$A_{jj}=0$$ , it implies $$A_{jk}=1$$ $$($$otherwise rows i and j would be orthogonal, which is impossible by $$AA^t_{ij}>0)$$.

Again, since $$A_{kk}=0$$ , it implies $$A_{kj}=1$$ $$($$otherwise rows i and k would be orthogonal, which is impossible by $$AA^t_{ik}>0)$$.

Now $$A^t_{jk}+A_{jk}=A_{kj}+A_{jk}=2>1$$, which contradicts the equation $$A+A^t+Id=EE^t$$.