# Prove that the set of $n$-by-$n$ real matrices with positive determinant is connected

Math people:

In the fourth edition of Strang's "Linear Algebra and its Applications", page 230, he poses the following problem (I have changed his wording): show that if $A \in \mathbf{R}^{n \times n}$ with $\det(A) >0$, then there exists a continuous function $f:[0,1] \to \mathbf{R}^{n \times n}$ with $f(0) = I$, $f(1) = A$, and $\det(f(t)) > 0$ for all $t \in [0,1]$. He says "the problem is not so easy, and solutions are welcomed by the author" (direct quote from the book). Since the author welcomes solutions, I am not 100% sure even he has solved it. Does anyone know if this is true or false, and may I have a solution or a hint? I assigned this problem to a graduate student in a linear algebra class, because I wanted to give him a challenge. Neither one of us has solved it. I have a lot of other things to do, but I'd like to give him a hint.

STEFAN (Stack Exchange FAN)

-

To continuosly transform $A$ to $I$, you can perform "continuous row and column operations" as these don't change the determinant:

1. Ensure that $a_{n,n}\ne0$, by continuously adding some other row to row $n$ if necessary (the existence of such a row is guaranteed by $\det A\ne 0$).
2. Continouusly subtract a multiple of the $n$th row from all other rows until $a_{in}=0$ for all $i< n$. Also substract the $n$th column continuously from all other columns to ensure $a_{ni}=0$ for $i<n$
3. Now recurse, i.e. perform steps 1 and 2 with the top left $(n-1)\times (n-1)$ submatrix etc. In the end you have a diagonal matrix with unchanged determinant

By now you have a diagonal matrix with the original positive determinant, hence negative entries come in pairs. Such negative pairs can be continuously made postive as follows by row and column operations:

$$\begin{pmatrix}-a&0\\0 &-b\end{pmatrix}\to \begin{pmatrix}-a&0\\-a &-b\end{pmatrix}\to \begin{pmatrix}0&b\\-a &-b\end{pmatrix}\to\begin{pmatrix}0&b\\-a &0\end{pmatrix}\\ \to\begin{pmatrix}b&b\\-a &0\end{pmatrix} \to\begin{pmatrix}b&0\\-a &a\end{pmatrix} \to\begin{pmatrix}b&0\\0 &a\end{pmatrix}$$ Now we have a diagonal matrix with positive entries, and these can be continuously changed to $1$, thus producing $I$. Note that only this last step changed the determinant at all.

I specifically wanted to avoid rotating vectors with transcendental functions. Instead, the resulting curve above is piecewise linear and if we start with rational $A$ we can have rational matrices at every rational time $t$.

-
Excellent! (Mandatory extra characters) –  Stefan Smith Feb 26 '13 at 23:43
This really is very nice!!! +1 –  user1551 Feb 27 '13 at 1:11
@StefanSmith A useful tip: you can pad comments to circumvent the character floor by including dollar signs. Each pair will cancel. –  Potato Feb 28 '13 at 4:00

This is true. Sketch: use Gram-Schmidt to connect $A$ to an orthogonal matrix, then use the spectral theorem.

-
Wow, that was fast. We haven't done the Gram-Schmidt process in our class yet, so my student will have to wait. I upvoted your answer. I will accept it unless I get an answer that's more fleshed-out within a day or two. –  Stefan Smith Feb 26 '13 at 23:18
Sorry, I accepted the answer below because it is more elementary and doesn't require the high-powered theorems. I just noticed that the Gram-Schmidt process comes before determinants in Strang's book, though I did determinants first. –  Stefan Smith Feb 26 '13 at 23:46

Approach -1: Transvections/Elementary matrices (Clearly the most efficient of the four proofs I give below).

Let $A$ be a real $n\times n$ matrix with positive determinant.

First connect it to a determinant $1$ matrix within positive determinant matrices by $A_t:=\left(\sqrt[n]{(1-t)\mbox{det}A^{-1}+t} \right)\;A$.

Now recall that $SL_n(\mathbb{R})$ is generated by the transvections (elementary matrices) $T_{i,j}=I_n+E_{i,j}$ for $i\neq j$ where $E_{i,j}$ is the matrix $1$ in $(i,j)$ position and $0$ elsewhere.

Note the path $I_n+tE_{i,j}$ connects $T_{i,j}$ to $I_n$ in $SL_n(\mathbb{R})$.

The result follows.

Approach 0: $LU$ decomposition.

Take $A$ a real $n\times n$ matrix with positive determinant. There exist a permutation matrix $P$, alower triangular matrix $L$ and an upper triangular matrix $U$ such that $$A=PLU.$$

First decompose $P$ as a product of transposition matrices. Then note that the path $$\left(\matrix{\cos(\pi t/2)&\sin(\pi t/2)\\\sin(\pi t/2)&-\cos(\pi t/2)}\right)$$ connects $$\left(\matrix{0&1\\1&0}\right)\quad\mbox{and}\quad\left(\matrix{1&0\\0&-1}\right).$$ It follows that we can connect $P$ to a diagonal matrix with coeffients in $\{-1,1\}$ with determinant constant equal to $\mbox{det}P$.

Now let $L_t$ and $U_t$ be the matrices obtained from $L$ and $U$ respectively by multiplying the off-diagonal coefficients by $t$. Then $L_tU_t$ is a continuous path from $A$ to a diagonal matrix, with determinant constant equal to $\mbox{det}L\cdot \mbox{det}U$.

Combining both paths for $P$ and $LU$, we connect $A$ to a diagonal matrix with constant determinant equal to $\mbox{det}A$.

Now every diagonal matrix with positive determinant can be connected to $I_n$ by a path with positive determinant.

It suffices to do it for diagonal matrices with coefficients in $\{-1,1\}$, since every diagonal matrix with positive determinant can easily be connected to such a diagonal matrix within positive determinant matrices.

Now it is clear that it only remains to show that $$\left( \matrix{-1&0\\0&-1}\right)$$ is connected to $I_2$ within the $2\times 2$ matrices with positive determinant.

Here is such a path: $$\left( \matrix{\cos(\pi t)&\sin(\pi t)\\-\sin(\pi t)&\cos(\pi t)}\right).$$

Approach 1: Singular value decomposition.

We will also use the fact that the set of all real $n\times n$ unitary (=orthogonal) matrices has two arcwise connected components. The one where the determinant equals $1$, and the one where it equals $-1$. This is easy to show by diagonalization in an orthonormal basis. It amounts to showing that $$\left( \matrix{-1&0\\0&-1}\right)$$ is connected to $I_2$ within the $2\times 2$ orthogonal matrices.

The same path as in approach 0 works.

Let $A$ be an $n\times n$ real matrix with positive determinant, and let $\mathcal P$ denote this set. We will show that $A$ can be connected to the identity matrix $I_n$ within $\mathcal{P}$.

Let $A=U\Sigma V$ be the singular value decomposition of $A$. Recall that $U$ and $V$ are unitary real $n\times n$ matrices, and that $\Sigma$ is a diagonal matrix with nonnegative entries. In this case, this means that the diagonal coefficients of $\Sigma$ are all positive.

Since $\mbox{det}A>0$, it follows easily that $\mbox{det}U=\mbox{det}V$.

Now take a path $U_t$ from $U$ to $I_n$ and a path $V_t$ from $V$ to $I_n$ within the real unitary matrices. By continuity of the determinant, $\mbox{det}U_t=\mbox{det}V_t=\mbox{det}U=\mbox{det}V$ for all $t$.

So the path $$U_t\Sigma V_t$$ connects $A$ to $\Sigma$ within $\mathcal P$.

It only remains to connect $\Sigma$ to $I_n$ within $\mathcal P$, which is extremely easy.

Approach 2: Jordan normal form of a real square matrix.

Take a real $n\times n$ matrix $A$ with positive determinant,

First note that if $B_t$ is a path within $\mathcal P$ from $B$ to $I_n$, and if $P$ is invertible, then $P^{-1}B_tP$ is a path from $P^{-1}BP$ to $I_n$ within $\mathcal{P}$. So it suffices to prove the claim for $A$ in Jordan normal form.

So let $A$ be in Jordan normal form with positive determinant.

Now let $A_t$ be the matrix obtained from $A$ by multiplying each off diagonal coefficient by $t$. This connects $A$ to a diagonal matrix within $\mathcal P$.

So it boils down to showing that every diagonal matrix with positive determinant can be connected to $I_n$ in $\mathcal{P}$. See the end of approach 0.

-
@Stefan: if the term "triangularizable" did not exist, how would you state the theorem "every square matrix is triangularizable"? –  Qiaochu Yuan Feb 27 '13 at 0:30
–  Stefan Smith Feb 28 '13 at 1:39

A proof using action of groups:

Let $GL_n(\mathbb{R})_+= \{ M \in GL_n(\mathbb{R}) \mid \det(M)>0 \}$ act on $\mathbb{R}^n \backslash \{0\}$ in the canonical way; notice that the action is transitive. Let $e_1=(1,0,...,0)$.

Introduce the subgroups $H$ and $K$ defined by $H= \left\{ \left( \begin{array}{cc} 1 & 0 \dots 0 \\ \begin{array}{c} 0 \\ \vdots \\ 0 \end{array} & A \end{array} \right) \mid A \in GL_{n-1}(\mathbb{R})_+ \right\}$ and $G= \left\{ \left( \begin{array}{cc} 1 & a_1 \dots a_{n-1} \\ \begin{array}{c} 0 \\ \vdots \\ 0 \end{array} & I_{n-1} \end{array} \right) \mid (a_1,...,a_{n-1}) \in \mathbb{R}^{n-1} \right\}$. Then the stabilizer of $e_1$ is $HG$, homeomorphic to $G \times H \simeq \mathbb{R}^{n-1} \times GL_{n-1}(\mathbb{R})_+$.

You deduce that $\mathbb{R}^{n}\backslash \{0\}$ is homeomorphic to $GL_n(\mathbb{R})_+ /( \mathbb{R}^{n-1} \times GL_{n-1}(\mathbb{R}_+))$. Finally, you can conclude by induction using the following lemma:

Lemma: Let $G$ be a topological group and $H$ be a subgroup of $G$. If $H$ and $G/H$ are connected, then $G$ is connected.

Proof: Let $f : G \to \{0,1\}$ be a continuous function. Since $H$ is connected, $f$ is constant on the classes of $G$ modulo $H$, hence a continuous function $\tilde{f} : G/H \to \{0,1\}$. But $G/H$ is connected, so $\tilde{f}$ is constant. You deduce that $f$ is constant, hence $G$ is connected. $\square$

-