Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question

4 Answers 4

up vote 19 down vote accepted

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

share|improve this answer
    
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
2  
@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.

share|improve this answer
    
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.

share|improve this answer
    
@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
    
let us continue this discussion in chat –  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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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