# Bounding entries of the inverse of certain zero-one matrices

It is known that the entries of the inverse of an (invertible) $n \times n$ zero-one matrix $A$ can grow exponentially in $n$. See this MO question: Bounding the absolute sum of entries of the inverse of a 0-1 matrix.

What if $A$ is known to have constant column sums (so a multiple of a stochastic matrix)? Or, more generally, what if we have bounds on the entries of $A^\top A$?

In the first question (with no additional constraints on $A$), Noam Elkies gives an interesting example in which $A_{ij}=1$ if and only if $j=i$, $j=i+1$ or $j=i+3$. Interpreting these (mod $n$) leads to only three more ones in the (now circulant) matrix, yet the inverse becomes well-behaved.

• The counterexample in the question you linked to is very close to having constant column sums, so it's clear that this condition can't help. – Christian Remling Apr 30 '16 at 1:35
• Please see my last paragraph. If you adjust Elkies' example to have constant column sum, it fails to have large inverse. The inverse of the circulant has all entries less than one in absolute value. Indeed, being a multiple of a stochastic matrix, we would expect small column sums in the inverse. – Peter Dukes Apr 30 '16 at 3:00

Let $A$ be a matrix with column sums at most $3$ with large elements in the inverse matrix. Construct a matrix of the form $\begin{pmatrix}A&0\\B&C\end{pmatrix}$, where $B$ is a $4\times n$ matrix and $C$ is a $4\times 4$ matrix. You may do this so that the resulting matrix has constat column sums (equal to $3$) and is non-degenerate. The inverse of this matrix contains $A^{-1}$ in the upper-left corner.