If $A$ is a fully indecomposable matrix then so is $AA^t$.

There is this problem in A Course in Combinatorics by Van Lint Wilson (problem 12B):

Let $A=[a_{ij}]$ be a fully indecomposable $n\times n$ matrix with $a_{ij}\geq 0$ for all $i,j={1,\cdots n}$. Show that $AA^T$ is also fully indecomposable.

I think this is generally true for any fully indecomposable $A,B$ but I couldn't prove it.

Update: There is a hint at the end:

Suppose $AA^t$ is decomposable. Explain the block of $0$ entries by considering some row of A, its nonzero entries, and the inner products with other rows.

So let's assume that $AA^t$ is decomposable, meaning that $$AA^t=\begin{bmatrix} B &C\\ 0 &D \end{bmatrix}$$ in which the size of the zero block is $k\times (n-k)$. Therefore, we have $$A_{n-k+1}\cdot A_1=A_{n-k+2}\cdot A_1=\cdots =A_{n}\cdot A_1=0\\A_{n-k+1}\cdot A_2=A_{n-k+2}\cdot A_2=\cdots =A_{n}\cdot A_2=0\\ \vdots \\ A_{n-k+1}\cdot A_{n-k}=A_{n-k+2}\cdot A_{n-k}=\cdots =A_{n}\cdot A_{n-k}=0$$ Where $A_i$ is the $i$th row of $A$. Now we still haven't used the fact that the entries are nonnegative. Take one of the inner products above, like $A_i\cdot A_j=0$ ($n-k+1\leq i\leq n, 1\leq j \leq n-k)$, this is $$a_{i1}a_{j1}+a_{i2}a_{j2}+\cdots +a_{in}a_{jn}=0$$ Since the entries are nonnegative, we get that for each $k\in \{1,2,\cdots ,n\}$, at least one of $a_{ik}$ and $a_{jk} $ is zero.

Now all that is left is to use this information and find a $s\times (n-s)$ zero submatrix of $A$. But I'm stuck here (since forever!!). I need help to finish my argument.

Let $v\in\mathbb{R}^n$ and $A_{n\times n}\in \mathbb{R}^{n\times n}$. If their entries are non-negative then we write $v\geq 0$ and $A\geq 0$.

Now, define $N(v)=$ the number of positive entries of $v$.

Lemma: $A_{n\times n}\geq 0$ is fully indecomposable iff $N(Av)>N(v)$ for every $v\geq 0$ such that $n>N(v)>0$.

Corollary 1: If $A_{n\times n}\geq 0$ is fully indecomposable then $N(Av)\geq N(v)$ for every $v\geq 0$.

Corollary 2: Let $A_{n\times n},B_{n\times n}\geq 0$. If $A,B$ are fully indecomposable then $AB$ is too.

By corollary 2, you just need to choose $B=A^t$.

Proof of the Corollary 2: Let $v\geq 0$ be such that $n>N(v)>0$.

By corollary 1, $N(ABv)\geq N(Bv)$. By the lemma, $N(Bv)>N(v).$ So, by the lemma, $AB$ is fully indecomposable too. $\square$

Proof of Lemma: If $A$ is not fully indecomposable then there are permutation matrices $P,Q$ such that $PAQ=\begin{pmatrix} X_{s\times s} & Y\\ 0_{n-s\times s}& Z\end{pmatrix}$. Let $v\in \mathbb{R}^n$ be such that $v_1=\ldots=v_s=1$ and $v_k=0$ for $k>s$.

Notice that $N(PAQv)\leq s=N(v)$. Hence, $$N(Qv)=N(v)\geq N(PAQv)=N(AQv).$$

Now, for the opposite direction, assume that there is $w\in \mathbb{R}^n$ such that $n>N(w)>0$ and $N(w)\geq N(Aw)$.

Let $s=N(w)$, $t=N(Aw)$ and $e_1,\ldots,e_n$ be the canonical basis of $\mathbb{R}^n$.

Let $P$ be a permutation matrix such that $PAw\in span\{e_1,\ldots,e_t\}$.

Let $Q$ be a permutation matrix such that $Q^{-1}w=\sum_{i=1}^s w_ie_i$, $w_i>0$ for $1\leq i\leq s$.

Then $\sum_{i=1}^s w_i(PAQ)e_i=(PAQ)(Q^{-1}w)=PAw\in span\{e_1,\ldots,e_t\}$.

Since $PAQ\geq 0$ and $w_i>0$, for $1\leq i\leq s$, $(PAQ)e_i\in span\{e_1,\ldots,e_t\}\subset span\{e_1,\ldots,e_s\}$, for $1\leq i\leq s$.

So $PAQ=\begin{pmatrix} X_{s\times s} & Y\\ 0_{n-s\times s}& Z\end{pmatrix}$. Thus, $A$ is not fully indecomposable. $\square$

Proof of Corollary 1: If $v=0$ then $Av=0$.

Next, by lemma 1, it remains to show that if all the entries of $v$ are positive then all the entries of $Av$ are positive.

Let $v=(v_1,\ldots,v_n)^t=(v_1,\ldots, v_{n-1},0)^t+(0,\ldots,0,v_{n})^t$.

Notice that $N(A(v_1,\ldots, v_{n-1},0)^t)>N((v_1,\ldots, v_{n-1},0)^t)$ by lemma 1. Thus, $N(A(v_1,\ldots, v_{n-1},0)^t)=n$.

Now, $N(Av)\geq N(A(v_1,\ldots, v_{n-1},0)^t)=n$. $\square$