[Home]

$ \newcommand{\v}{\vec} \newcommand{\nul}{{\mathcal N}} $ Matrix decompositions Often it is useful to be able to express a matrix as a product of matrices with simple structures (eg, diagonal, triangular, orthogonal etc). There is a trade-off in such decompositions: how general can the input matrix be, and how simple the output matrices. We list here a few useful decompositions.

$QR$ decomposition

Theorem Every complex matrix $A_{m\times n}$ can be decomposed as $A = QR,$ where $Q_{m\times m}$ is a unitary matrix and $R_{m\times n}$ is an upper triangular matrix.

The result also has an analogue in ${\mathbb R}:$

Theorem Every real matrix $A_{m\times n}$ can be decomposed as $A = QR,$ where $Q_{m\times m}$ is an orthogonal matrix and $R_{m\times n}$ is an upper triangular matrix.

This is just applying GSO on columns of $A.$ For example if $A=\left[\begin{array}{ccccccccccc}2 & 3\\0 & 4\\0 & 0 \end{array}\right],$ then $GSO$ on the two columns will produce $\left[\begin{array}{ccccccccccc}1\\0\\0 \end{array}\right]$ and $\left[\begin{array}{ccccccccccc}0\\1\\0 \end{array}\right].$ The columns of $A$ can be expressed as a linear combination of these: $$ \left[\begin{array}{ccccccccccc}2\\0\\0 \end{array}\right] = 2\left[\begin{array}{ccccccccccc}1\\0\\0 \end{array}\right] $$ and $$ \left[\begin{array}{ccccccccccc}3\\4\\0 \end{array}\right] = 3\left[\begin{array}{ccccccccccc}1\\0\\0 \end{array}\right] + 4\left[\begin{array}{ccccccccccc}0\\1\\0 \end{array}\right]. $$ If we write this in matrix form we get $$ \left[\begin{array}{ccccccccccc}2 & 3\\0 & 4\\0 & 0 \end{array}\right] = 3\left[\begin{array}{ccccccccccc}1 & 0\\0 & 1\\0 & 0 \end{array}\right]\left[\begin{array}{ccccccccccc}2 & 3\\0 & 4 \end{array}\right]. $$ Well, that is alomost the $QR$ decomposition, except that $\left[\begin{array}{ccccccccccc}1 & 0\\0 & 1\\0 & 0 \end{array}\right]$ is not square, and so cannot be unitary. To remdy this we extend the output of the GSO to an ONB of ${\mathbb R}^3$ to get $Q = I.$ We also add a null row at the bottom of $R$ to make sure that this extension has no effect in the decomposition: $R = \left[\begin{array}{ccccccccccc}2 & 3\\0 & 4\\0 & 0 \end{array}\right].$

However, GSO is not the best computational way to compute $QR$ decomposition.

SVD

Theorem Every complex matrix $A_{m\times n}$ can be decomposed as $A = UDV^*,$ where $U_{m\times m}$ and $V_{n\times n}$ are both unitary and $D_{m\times n}$ is diagonal with leading $r$ diagonal entries $>0,$ the rest being $0.$ Here $r=r(A).$

There is an ${\mathbb R}$-version as well:

Theorem Every real matrix $A_{m\times n}$ can be decomposed as $A = UDV',$ where $U_{m\times m}$ and $V_{n\times n}$ are both orthogonal and $D_{m\times n}$ is diagonal with leading $r$ diagonal entries $>0,$ the rest being $0.$ Here $r=r(A).$

Schur decomposition

Theorem Every complex square matrix $A$ can be decomposed as $A = PTP^*,$ where $T$ is upper triangular matrix and $P$ is an unitary matrix.

Unfortunately, this has no analog over field ${\mathbb R}.$

Spectral decomposition

Theorem Every complex Hermitian matrix $A$ can be decomposed as $A = PDP^*,$ where $D$ is diagonal (with real entries) and $P$ is a unitary matrix.

This has an ${\mathbb R}$-version:

Theorem Every real symmetric matrix $A$ can be decomposed as $A = PDP',$ where $D$ is diagonal (with real entries) and $P$ is an orthogonal matrix.

Cholesky decomposition

Theorem Every PD matrix $A_{n\times n}$ can be uniquely decomposed as $A = BB',$ where $B_{n\times n}$ is a lower triangular matrix.

This result is over ${\mathbb R}.$ While it is possible to have an analogous result over ${\mathbb C},$ it is rarely used.

Before we head for the proof, it will help to look at an example. Suppose $$ A= \left[\begin{array}{ccccccccccc} 4 & 1\\1&9 \end{array}\right]. $$ Then (assuming the existence of a Cholesky decomposition) we can write $A=B B'$ for some $B=\left[\begin{array}{ccccccccccc}a & 0\\b & c \end{array}\right].$ So we must have $$ \left[\begin{array}{ccccccccccc}a^2 & ab\\ ab & b^2+c^2 \end{array}\right] = \left[\begin{array}{ccccccccccc} 4 & 1\\1&9 \end{array}\right]. $$ Notice that $a,b$ and $c$ can be recovered from this uniquely (since $a,c>0$). Convince yourself that this may be generalised to any $n\times n$ PD matrix to compute Cholesky decomposition (assuming that one exists).

Proof: The existence of a Cholesky decomposition is proved by induction on $n.$ It is obvious for $n=1.$ Assume up to $n-1.$

Shall show for $n.$

Since the leading principal $n-1\times n-1$ submatrix of $A$ is again $NND,$ hence it can be decomposed as $C'C$ for some upper triangular $C.$ Thus, $$ A = \left[\begin{array}{ccccccccccc}CC' & \v a\\\v a' & \alpha. \end{array}\right] $$ Let's do a little rough work:

Suppose we can decompose $A$ as $A=BB'$ where $B = \left[\begin{array}{ccccccccccc}N & \v 0\\\v x' & y \end{array}\right].$
Then $$ A = \left[\begin{array}{ccccccccccc}N & \v 0\\\v x' & y \end{array}\right]\left[\begin{array}{ccccccccccc}N' & \v x\\\v 0' & y \end{array}\right] = \left[\begin{array}{ccccccccccc}NN' & N\v x\\\v x'N' & \v x' \v x+y^2 \end{array}\right]. $$ Thus, if we partition $A$ as $\left[\begin{array}{ccccccccccc}M & \v p\\\v p' & q \end{array}\right]$, then $\v p$ must be $N\v x$ and $q = \v x'\v x+y^2.$

With this rough work in mind, we are now ready to proceed with the proof.

Partition $A$ as $A=\left[\begin{array}{ccccccccccc}M & \v p\\\v p' & q \end{array}\right].$

Then by standard result about PD matrices we know that $M$ must be PD, and hence $M=NN'$ for some nonsingular $N.$

Define $\v x = N ^{-1} \v p.$

Then $q-\v x'\v x> 0.$

Because: $q-\v x'\v x = q-\v p' (N'N)^{-1} \v p = \frac{|A|}{|M|} > 0. $

Define $y = \sqrt{q-\v x'\v x}.$

Then it is trivial to check that $A = B B',$ where $B = \left[\begin{array}{ccccccccccc}N & \v 0\\\v x' & y \end{array}\right].$ [QED]

Jordan Canonical Form (JCF)

Definition A matrix with diagonal entries all equal and supr diagonal entries all $1,$ and all other entries $0,$ is called a Jordan block. It is fully spcified by the common diagonal entry and its size. If the diagonal entry is $\lambda,$ and the size is $k\times k$ then we shall denote it by $J_k(\lambda).$

For example, $$ J_1(2) = [2],~~ J_2(2) = \left[\begin{array}{ccccccccccc}2 & 1\\0 &2 \end{array}\right],~~ J_3(2) = \left[\begin{array}{ccccccccccc}2 & 1 & 0\\0 &2 & 1\\0 & 0 & 2 \end{array}\right]. $$

Definition A square matrix is said to be in JCF if it is block diagonal matrix with each block being a Jordan block.

Theorem (Existence) Every square matrix over ${\mathbb C}$ is similar to a matrix in JCF.

Theorem (Uniqueness) Two matrices in JCF are similar if and only if they both have the same Jordan blocks the same number of times possibly in a different order.

The consequence of these two theorems is the following theorem:

Theorem Two square matrices $A,B$ are similar if and only if $A$ is similar to $J_A$ in JCF and $B$ is similar to $J_B$ in JCF, and $J_A$ and $J_B$ constain the same blocks in possibly a different order. matrix in JCF.

Proof: Let $A\sim J_A$ and $A\sim J_B$, where $J_A$ and $J_B$ consist of the same blocks in possibly some different order. Then the uniqueness theorem says $J_A\sim J_B.$ Hence $$ A\sim J_A\sim J_B\sim B. $$ Conversely, Let $A\sim B.$. By the existence theorem you can get JCF matrices $JA$ and $J_B$ such that $A\sim J_A$ and $B\sim J_B.$

So $$ J_A\sim A\sim B\sim J_B. $$ Hence, by the uniqueness theorem, $J_A$ and $J_B$ must contain the same block in possibly some different order. can get their JCF's, and these two JCF matrices must be similar. By the second theorem the JCF matrices must have the same blocks in possibly some diferent orders. [QED]

The proof of the uniqueness theorem is quite easy, and may be done via the following steps.

Show that if $J$ is JCF, then its eigenvalues are the diagonal entries, each repeated as many times as its algebraic multiplicity. (In fact, this is true for any triangular matrix.) Hence, if $J_A\sim J_B$ then their diagonal entries must be the same (except possibly in order).
Show that for $p=1,...,k$ we have $r(J_k(0)^p) = k-p.$
Let $J$ is in JCF, and let $N_p$ be the number of $\lambda$-blocks of size $p.$
Then show that for any $j=1,...,n$ we have $$ r((J-\lambda I)^i) = N_{i+1}+2N_{i+2}+\cdots+(n-i) N_n + \mbox{sum of sizes of all other blocks.} $$
Conclude the uniqueness theorem from the above.

We shall not prove the existence theorem here, but provide the main idea. Each red word marks a point requiring some nontrivial argument.

The theorem may be proved by induction. W.l.g., that our matrix has only one distinct eigenvalue, $0.$

Note that then $A$ nilpotent. Let $k\in{\mathbb N}$ be the smallest integer such that $A^k=O$ (this $k$ is sometimes called the index of nilpotency). Since $A^{k-1}\neq O,$ hence we can find $\v v$ such that $A^{k-1}\v v\neq \v0.$ Define $$ S = span\{\v v,A\v v,...,A^{k-1}\v v\}. $$ Note that $S$ is invariant under $A,$ if $\v x\in S$ then $A\v x \in S.$

If $S = {\mathbb C}^n$ then the existence is proved easily.

Othwerwise, we find a direct complement $T$ of $S$ such that $T$ is also invariant under $A,$ ie, and if $\v x\in T$ then $A\v x \in T.$ (The difficult part of the proof lies in showing that such a $T$ must exist.)

This allows us to write $A$ is similar to $diag(A_S,A_T).$ Now we can apply the induction hypothesis on $A_S$ and $A_T$ separately.

We shall not pursue this further here.

Problems

Show that any $NND$ matrix $A$ may be decomosed as $B B'$ for some square matrix $B.$ [Hint: Proceed by induction on $n.$ Write $A=\left[\begin{array}{ccccccccccc}NN' & \v p\\\v p' & q \end{array}\right].$ Argue that $\v p=NN'\v s$ for some $\v s.$ Try something like $$ B = \left[\begin{array}{ccccccccccc}N & \v 0\\ \v s' N & t \end{array}\right] $$ for a suitable $t\in{\mathbb R}.$]
Show that the number of $\lambda$-blocks in a matrix in JCF is the geometric multiplicity of $\lambda.$
How many $4\times4$ complex matrices can you construct (distinct up to similarity) that have $2$ as the only eigenvalue having arithmetic multiplicity $4$ and geometric multiplicity $2$?
Obtain the JCF for $$ \left[\begin{array}{ccccccccccc} 1 & 2 & 3\\ 0 & 1 & 4\\ 0 & 0 & 2 \end{array}\right] $$
True/false: If a JCF matrix has at least one nonzero off-diagonal entry, then it must be defficient. Justify your answer.
Let $\lambda $ be an eigenvalue of $A.$ Call $\v v\neq\v 0$ a generalised eigenvector of $A$ corresponding to $\lambda,$ if $\v v\in \nul(A- \lambda I)^k$ for some $k=2,3,...$. Using JCF, show that for any square matrix $A$ over ${\mathbb C}$ there is a basis consisting of eigenvectors and generalised eigenvectors.
If the JCF of $A$ contains the block $J_5(2),$ then show that the minimal polynomial $p(\lambda)$ of $A$ is divisible by $(\lambda-2)^5.$

HTML Comment Box is loading comments...

Table of contents