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?
 A: 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$.
A: 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

*

*$(BB^t)_{ij}\geq (AA^t)_{ij}>0$, for $1\leq i,j\leq n$,

*$(BB^t)_{(n+1)j}\geq (AA^t)_{1j}>0$, for $1\leq j\leq n$, and

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