2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Christian Remling
    Commented Apr 30, 2016 at 1:35
  • $\begingroup$ 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. $\endgroup$
    – Peter Dukes
    Commented Apr 30, 2016 at 3:00

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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