4
$\begingroup$

My question is learned from here. Let me restate it as follows:

A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular.

Now suppose an $n\times n$ non-singular matrix $A$ is totally unimodular. Can we prove that $A^{−1}$ is also totally unimodular? Or if it is not correct, can we have a counterexample? Any help is much appreciated.

Edit: What I have already known is that the statement is true when $n=2$ and $3$. It follows from the definition of unimodular matrix and the fact that if $A$ is unimodular, then $$A^{-1}=\det A\cdot \mathrm{adj}(A)=\pm \mathrm{adj}(A).$$

$\endgroup$
  • $\begingroup$ I think this is true, but I cannot give a link. Nor do I recall the argument. IIRC if you pick a $k\times k$ minor of $A^{-1}$ it is equal to (up to sign and a factor that is a power of $\det A$ - so only sign here) the $(n-k)\times (n-k)$ minor of $A$ formed by the complementary sets of rows and columns. I have a vague recollection that a proof can be found in Jacobson, BA I-II in a chapter on exterior algebra, but cannot check now, as my copy is in my office. $\endgroup$ – Jyrki Lahtonen Apr 19 '13 at 19:52
  • $\begingroup$ @JyrkiLahtonen: Thank you for your comment. It is very helpful to me. With the tool of exterior algebra I think I can prove your statement now. $\endgroup$ – Hu Zhengtang Apr 20 '13 at 2:43
3
$\begingroup$

As commented by Jyrki Lahtonen, the statement is true and it is immediately implied by the following relation between the minors of $A^{-1}$ and the minors of $A$.

Proposition: If $A$ is an invertible $n\times n$ matrix, and if $i_1,\dots,i_n$ and $j_1,\dots,j_n$ be two permutations of $1,\dots,n$, then the minor of $A$ corresponding to rows $i_1,\dots,i_k$ and columns $j_1,\dots,j_k$, denoted by $d$, and the minor of $A^{-1}$ corresponding to rows $j_{k+1},\dots,j_n$ and columns $i_{k+1},\dots,i_n$, denoted by $d'$,satisfy that $$d=\pm d'\det A.$$

Proof: Let $e_1,\dots,e_n$ be a basis of $\mathbb{R}^n$, and let $f_i= A e_i$, $i=1,\dots,n$. Then on the one hand, $$\omega:=Ae_{j_1}\wedge\cdots\wedge Ae_{j_k}\wedge e_{i_{k+1}}\wedge \cdots\wedge e_{i_n}=\pm d\cdot e_1\wedge\cdots\wedge e_n,$$ on the other hand, $$\omega=f_{j_1}\wedge\cdots\wedge f_{j_k}\wedge A^{-1}f_{i_{k+1}}\wedge \cdots\wedge A^{-1}f_{i_n}=\pm d'\cdot f_1\wedge\cdots\wedge f_n.$$ Since $$f_1\wedge\cdots\wedge f_n=\det A\cdot e_1\wedge\cdots\wedge e_n,$$ the conclusion follows.

$\endgroup$
0
$\begingroup$

Here is a more elementary proof.

Theorem: The inverse of a (non-singular) totally unimodular matrix is totally unimodular.

The proof will use the following lemmas.

Lemma 1: Permuting rows and columns preserves total unimodularity.

Lemma 2: Matrix $A$ is totally unimodular if and only if the matrix $$ \begin{bmatrix} A & I \\ \end{bmatrix} $$ is totally unimodular (where $I$ is the identity matrix of the appropriate size).

Lemma 3: The pivot operation preserves total unimodularity.

(Pivot operation: choose a non-zero element $a_{i,j}$, called pivot. Multiply the $i$-th row by a scalar so that the pivot becomes 1. Then add multiples of the $i$-th row to all other rows so that all elements in column $j$ except pivot become 0.)

Proof of the theorem:

Let $A$ be a non-singular totally unimodular matrix. By Lemma 2, $\begin{bmatrix} A & I \end{bmatrix}$ is totally unimodular. By repeatedly applying pivot operations we obtain $\begin{bmatrix} I & A^{-1} \end{bmatrix}$ (basically doing Gaussian elimination on $A$). By Lemma 3, this matrix is totally unimodular, and by lemmas 1 and 2, $A^{-1}$ is totally unimodular. $\blacksquare$


Proof of Lemma 1: Let $A$ be totally unimodular, let $\tilde A$ obtained from $A$ by permuting rows and columns and let $\tilde B$ be a square submatrix of $\tilde A$. Then $\tilde B$ is also obtained by permuting some submatrix $B$ of $A$. Permuting rows and columns changes at most the sign of the determinant. Thus $\det(\tilde B) = \pm\det(B) \in \{-1,0,1\}$ $\blacksquare$

Proof of Lemma 2: Let $A$ be totally unimodular. Any square submatrix $B$ of $\begin{bmatrix} A & I\end{bmatrix}$ can be permuted to the form $$ \tilde B = \begin{bmatrix} A_1 & 0 \\ A_2 & I_k \\ \end{bmatrix}. $$ where $A_1$ is a square sub-matrix of $A$, and so $\det(A_1) \in \{-1,0,1\}$.

We have

$$ \det(B) = \pm\det(\tilde B) = \det(A_1) \in \{-1,0,1\}.$$

On the other hand, if $\begin{bmatrix} A & I\end{bmatrix}$ is totally unimodular, then since deleting columns preserves total unimodularity, $A$ is also totally unimodular. $\blacksquare$

Proof of Lemma 3: Let $A$ be totally unimodular and let $\tilde A$ be obtained from $A$ by the pivot operation with pivot $a_{i,j}$. Let $\tilde B$ be a square submatrix of $\tilde A$. We distinguish three cases:

  1. $\tilde B$ contains the pivot row $i$.
    Then $\tilde B$ was obtained from some $B$, a square submatrix of $A$, by (i) multiplying a row by $\pm1$ and (ii) adding multiples of that row to other rows. The operations (i) and (ii) preserve the determinant up to sign, so we have $\det(\tilde B) = \pm\det(B) \in \{-1, 0, 1\}$.
  2. $\tilde B$ does not contain the pivot row $i$, but contains the pivot column $j$. Since the column of $\tilde B$ corresponding to the pivot is all zeroes, we have $\det(\tilde B) = 0$.
  3. $\tilde B$ contains neither the pivot row nor the pivot column. Let $\tilde B_1$ be the matrix obtained from $\tilde B$ by adding the row and column of $\tilde A$ corresponding to the pivot. Since the column of $\tilde B_1$ corresponding to pivot has exactly one 1 and everything else 0, we have $\det(\tilde B) = \pm\det(\tilde B_1)$. But $\tilde B_1$ was obtained from some submatrix $B_1$ of $A$ by operations (as in 1.) that preserve determinant up to sign. So we have $\det(\tilde B) = \pm\det(\tilde B_1) = \pm\det(B_1) \in \{-1,0,1\}$. $\blacksquare$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.