1

Let $M\in GL_n(\mathbb{R})$ such that all its coefficients are non zero.

How can one show that $M^{-1}$ has at most $n^2-2n$ coefficients equal to zero ?

I have no idea how to tackle that problem, I've tried drawing some contradiction if $M^{-1}$ had $n^2+1-2n$ zero coefficients but couldn't find any.

Notations :

$GL_n(\mathbb{K})$ : Set of invertible matrices in $\mathcal{M}_n(\mathbb{K})$

Hippalectryon
  • 7,730

2 Answers2

4

Equivalently you need to prove that $M^{-1}$ has at least $2n$ nonzero entries. Let's in fact prove that every row of $M^{-1}$ had at least two nonzero entries. Suppose that the $i$th row of $M^{-1}$ has less than two nonzero entries; of course it cannot have a zero row (otherwise it would be singular), so it has exactly one nonzero entry. But then, in the equality $M^{-1}M = I$, we reach a contradiction, because in the $i$th row you would get: $$M^{-1} M = \begin{pmatrix} \dots &&&&&& \dots \\ 0 & \dots & 0 & a_{i,j} & 0 & \dots & 0 \\ \dots &&&&&& \dots \end{pmatrix} \times \begin{pmatrix} \vdots & b_{j,1} & \vdots \\ \vdots & \vdots & \vdots \\ \vdots & b_{j,n} & \vdots \end{pmatrix} = \begin{pmatrix} \dots && \dots \\ a_{i,j}b_{j,1} & \dots & a_{i,j}b_{j,n} \\ \dots && \dots \end{pmatrix}$$ And since all the entries of $M$ are nonzero, the $i$th row of $I$ would only have nonzero entries, which is absurd.

Najib Idrissi
  • 54,185
  • Would that work ? I suppose that $M^{-1}$ has one line with only one non zero coefficient, $M^{-1}M=\begin{bmatrix} 0&\dots&0&a_{1,k}&0&\dots&0 \a_{2,1}&&&\dots&&&a_{2,n} \ \dots \ a_{n,1}&&&\dots&&&a_{n,n} \end{bmatrix} \cdot \begin{bmatrix} b_{1,1}&&&\dots&&&b_{1,n} \ \dots \ \dots \ b_{n,1}&&&\dots&&&b_{n,n} \end{bmatrix} = \begin{bmatrix} b_{k,1}&b_{k,2}&&\dots&&&b_{k,n} \ \dots \ \dots \ \dots \end{bmatrix}$ , but $b_{k,2}\neq0$ therefore $M^{-1}M$ can't equal $I_n$ ? – Hippalectryon Oct 01 '14 at 19:09
  • Yes, that's it. – Najib Idrissi Oct 01 '14 at 19:11
1

Hint: Show that if there are at least $n^2-2n+1$ zeros, there will be a column of $M^{-1}$ with exactly 1 nonzero entry. Convince yourself that without loss of generality this might as well be the first column. Then convince yourself that $M M^{-1}$ will have the first column a multiple of one of the columns of $A$. Finally, see that this means $M M^{-1}$ cannot be the identity matrix since all the entries of $M$ are nonzero.

abnry
  • 14,664