Return to Question

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.

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.

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.

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.

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

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.