3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Aug 17, 2021 at 23:39

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
0
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .