Section ROD  Rank One Decomposition

From A First Course in Linear Algebra
Version 2.30
© 2004.
Licensed under the GNU Free Documentation License.
http://linear.ups.edu/

T h i s S e c t i o n i s a D r a f t, S u b j e c t t o C h a n g e s

Our first decomposition applies only to diagonalizable (Definition DZM) matrices, and yields a decomposition into a sum of very simple matrices.

Theorem  ROD
Rank One Decomposition
Suppose that $A$ is a diagonalizable matrix of size $n$ and rank $r$ . Then there are $r$ square matrices $A_1,A_2,A_3,\dots ,A_r$ , each of size $n$ and rank $1$ such that

$\begin{array}{llll}\hfill A& =A_1+A_2+A_3+\cdots +A_r& \hfill & \end{array}$

Furthermore, if ${\lambda }_1,{\lambda }_2,{\lambda }_3,\dots ,{\lambda }_r$ are the nonzero eigenvalues of $A$ , then there are two sets of $r$ linearly independent vectors from ${ℂ}^n$ ,

$\begin{array}{llllllll}\hfill X& =\left\{x_1,x_2,x_3,\dots ,x_r\right\}& \hfill Y& =\left\{y_1,y_2,y_3,\dots ,y_r\right\}& \hfill & & \hfill & \end{array}$

such that $A_k={\lambda }_k{x}_k{y}_k^t$ , $1\le k\le r$ . $\square$

Proof   The proof is constructive. Generally, we will diagonalize $A$ , creating a nonsingular matrix $S$ and a diagonal matrix $D$ . Then we split up the diagonal matrix into a sum of matrices with a single nonzero entry (on the diagonal). This fundamentally creates the decomposition in the statement of the theorem, the remainder is just bookkeeping. The vectors in $X$ and $Y$ will result from the columns of $S$ and the rows of $S^{-1}$ .

Let ${\lambda }_1,{\lambda }_2,{\lambda }_3,\dots ,{\lambda }_n$ be the eigenvalues of $A$ (repeated according to their algebraic multiplicity). If $A$ has rank $r$ , then $dim\left(\mathcal{N}\left(A\right)\right)=n-r$ (Theorem RPNC). The null space of $A$ is the eigenspace of the eigenvalue $\lambda =0$ (Theorem EMNS), so it follows that the algebraic multiplicity of $\lambda =0$ is $n-r$ , ${\alpha }_A\left(0\right)=n-r$ . Presume that the complete list of eigenvalues is ordered so that ${\lambda }_k=0$ for $r+1\le k\le n$ .

Since $A$ is hypothesized to be diagonalizable, there exists a diagonal matrix $D$ and an invertible matrix $S$ , such that $D=S^{-1}AS$ . We can rearrange tis equation to read, $A=SD{S}^{-1}$ . Also, the proof of Theorem DC says that the diagonal elements of $D$ are the eigenvalues of $A$ and we have the flexibility to assume they lie on the diagonal in the same order as we have specified above. Now, let $X^{\ast }=\left\{x_1,x_2,x_3,\dots ,x_n\right\}$ be the columns of $S$ , and let $Y^{\ast }=\left\{y_1,y_2,y_3,\dots ,y_n\right\}$ be the rows of $S^{-1}$ converted to column vectors. With little motivation other than the statement of the theorem, define size $n$ matrices $A_k$ , $1\le k\le n$ by $A_k={\lambda }_k{x}_k{y}_k^t$ . Finally, let $D_k$ be the size $n$ matrix that is totally zero, other than having ${\lambda }_k$ in row $k$ and column $k$ .

With everything in place, we compute entry-by-entry,

$\begin{array}{llllllll}\hfill {\left[A\right]}_{ij}& ={\left[SD{S}^{-1}\right]}_{ij}& \hfill & \text{Definition DZM}& \hfill & & \hfill & \\ \hfill & ={\left[S\left(\sum _{k=1}^n{D}_k\right)S^{-1}\right]}_{ij}& \hfill & \text{Definition MA}& \hfill & & \hfill & \\ \hfill & ={\left[S\left(\sum _{k=1}^n{D}_k{S}^{-1}\right)\right]}_{ij}& \hfill & \text{Theorem MMDAA}& \hfill & & \hfill & \\ \hfill & ={\left[\sum _{k=1}^{n}S{D}_k{S}^{-1}\right]}_{ij}& \hfill & \text{Theorem MMDAA}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\left[S{D}_k{S}^{-1}\right]}_{ij}& \hfill & \text{Definition MA}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n\sum _{\ell =1}^n{\left[S{D}_k\right]}_{i\ell }{\left[S^{-1}\right]}_{\ell j}& \hfill & \text{Theorem EMP}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n\sum _{\ell =1}^n\sum _{p=1}^n{\left[S\right]}_{ip}{\left[D_k\right]}_{p\ell }{\left[S^{-1}\right]}_{\ell j}& \hfill & \text{Theorem EMP}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\left[S\right]}_{ik}{\left[D_k\right]}_{kk}{\left[S^{-1}\right]}_{kj}& \hfill & {\left[D_k\right]}_{p\ell }=0\text{ if }p\ne k\text{, or }\ell \ne k& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\left[S\right]}_{ik}{\lambda }_k{\left[S^{-1}\right]}_{kj}& \hfill & {\left[D_k\right]}_{kk}={\lambda }_k& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\lambda }_k{\left[S\right]}_{ik}{\left[S^{-1}\right]}_{kj}& \hfill & \text{Property CMCN}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\lambda }_k{\left[x_k\right]}_{i1}{\left[y_k^t\right]}_{1j}& \hfill & \text{ Definition of }{X}^{\ast }\text{, }{Y}^{\ast }& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\lambda }_k\sum _{q=1}^1{\left[x_k\right]}_{iq}{\left[y_k^t\right]}_{qj}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\lambda }_k{\left[x_k{y}_k^t\right]}_{ij}& \hfill & \text{Theorem EMP}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\left[{\lambda }_k{x}_k{y}_k^t\right]}_{ij}& \hfill & \text{Definition MSM}& \hfill & & \hfill & \\ \hfill & =\sum _{k=1}^n{\left[A_k\right]}_{ij}& \hfill & \text{ Definition of }{A}_k& \hfill & & \hfill & \\ \hfill & ={\left[\sum _{k=1}^n{A}_k\right]}_{ij}& \hfill & \text{Definition MA}& \hfill & & \hfill & \\ \hfill & & \hfill & & \hfill \end{array}$

So by Definition ME we have the desired equality of matrices. The careful reader will have noted that $A_k=\mathcal{O}$ , $r+1\le k\le n$ , since ${\lambda }_k=0$ in these instances. To get the sets $X$ and $Y$ from $X^{\ast }$ and $Y^{\ast }$ , simply discard the last $n-r$ vectors. We can safely ignore (or remove) $A_{r+1},A_{r+2},\dots ,A_n$ from the summation just derived.

One last assertion to check. What is the rank of $A_k$ , $1\le k\le r$ ? Every row of $A_k$ is a scalar multiple of $y_k^t$ , row $k$ of the nonsingular matrix $S^{-1}$ ( Theorem MIMI). As a row of a nonsingular matrix, $y_k^t$ cannot be all zeros. In particular, row $i$ of $A_k$ is obtained as a scalar multiple of $y_k^t$ by the scalar ${\alpha }_k{\left[x_k\right]}_i$ . We have restricted ourselves to the nonzero eigenvalues of $A$ , and as $S$ is nonsingular, some entry of $x_k$ is nonzero. This all implies that some row of $A_k$ will be nonzero. Now consider row-reducing $A_k$ . Swap the nonzero row up into row 1. Use scalar multiples of this row to zero out every other row. This leaves a single nonzero row in the reduced row-echelon form, so $A_k$ has rank one. $■$

We record two observations that was not stated in our theorem above. First, the vectors in $X$ , chosen as columns of $S$ , are eigenvectors of $A$ . Second, the product of two vectors from $X$ and $Y$ in the opposite order, by which we mean $y_i^t{x}_j$ , is the entry in row $i$ and column $j$ of the matrix product $S^{-1}S=I_n$ ( Theorem EMP). In particular,

$\begin{array}{llll}\hfill y_i^t{x}_j& =\left\{\begin{array}{cc}1\hfill & \text{ if }i=j\hfill \\ 0\hfill & \text{ if }i\ne j\hfill \end{array}\right.& \hfill & \end{array}$

We give two computational examples. One small, one a bit bigger.

Example  ROD2
Rank one decomposition, size 2
Consider the $2\times 2$ matrix,

$\begin{array}{llll}\hfill A& =\left[\begin{array}{cc}\hfill -16\hfill & \hfill -6\hfill \\ \hfill 45\hfill & \hfill 17\hfill \end{array}\right]& \hfill & \end{array}$

By the techniques of Chapter E we find the eigenvalues and eigenspaces,

$\begin{array}{llllllllllllllll}\hfill {\lambda }_1& =2& \hfill {\mathcal{ℰ}}_A\left(2\right)& =〈\left\{\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 3\hfill \end{array}\right]\right\}〉& \hfill {\lambda }_2& =-1& \hfill {\mathcal{ℰ}}_A\left(-1\right)& =〈\left\{\left[\begin{array}{c}\hfill -2\hfill \\ \hfill 5\hfill \end{array}\right]\right\}〉& \hfill & & \hfill & & \hfill & & \hfill & \end{array}$

With $n=2$ distinct eigenvalues, Theorem DED tells us that $A$ is diagonalizable, and with no zero eigenvalues we see that $A$ has full rank. Theorem DC says we can construct the nonsingular matrix $S$ with eigenvectors of $A$ as columns, so we have

$\begin{array}{llllllll}\hfill S& =\left[\begin{array}{cc}\hfill -1\hfill & \hfill -2\hfill \\ \hfill 3\hfill & \hfill 5\hfill \end{array}\right]& \hfill S^{-1}& =\left[\begin{array}{cc}\hfill 5\hfill & \hfill 2\hfill \\ \hfill -3\hfill & \hfill -1\hfill \end{array}\right]& \hfill & & \hfill & \end{array}$

From these matrices we obtain the sets of vectors

$\begin{array}{llllllll}\hfill X& =\left\{\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 3\hfill \end{array}\right],\left[\begin{array}{c}\hfill -2\hfill \\ \hfill 5\hfill \end{array}\right]\right\}& \hfill Y& =\left\{\left[\begin{array}{c}\hfill 5\hfill \\ \hfill 2\hfill \end{array}\right],\left[\begin{array}{c}\hfill -3\hfill \\ \hfill -1\hfill \end{array}\right]\right\}& \hfill & & \hfill & \end{array}$

And we have the matrices,

$\begin{array}{llll}\hfill A_1& =2\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 3\hfill \end{array}\right]{\left[\begin{array}{c}\hfill 5\hfill \\ \hfill 2\hfill \end{array}\right]}^t=2\left[\begin{array}{cc}\hfill -5\hfill & \hfill -2\hfill \\ \hfill 15\hfill & \hfill 6\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill -10\hfill & \hfill -4\hfill \\ \hfill 30\hfill & \hfill 12\hfill \end{array}\right]& \hfill & \\ \hfill A_2& =\left(-1\right)\left[\begin{array}{c}\hfill -2\hfill \\ \hfill 5\hfill \end{array}\right]{\left[\begin{array}{c}\hfill -3\hfill \\ \hfill -1\hfill \end{array}\right]}^t=\left(-1\right)\left[\begin{array}{cc}\hfill 6\hfill & \hfill 2\hfill \\ \hfill -15\hfill & \hfill -5\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill -6\hfill & \hfill -2\hfill \\ \hfill 15\hfill & \hfill 5\hfill \end{array}\right]& \hfill & \end{array}$

And you can easily verify that $A=A_1+A_2$ . $⊠$

Here’s a slightly larger example, and the matrix does not have full rank.

Example  ROD4
Rank one decomposition, size 4
Consider the $4\times 4$ matrix,

$\begin{array}{llll}\hfill B& =\left[\begin{array}{cccc}\hfill 34\hfill & \hfill 18\hfill & \hfill -1\hfill & \hfill -6\hfill \\ \hfill -44\hfill & \hfill -24\hfill & \hfill -1\hfill & \hfill 9\hfill \\ \hfill 36\hfill & \hfill 18\hfill & \hfill -3\hfill & \hfill -6\hfill \\ \hfill 36\hfill & \hfill 18\hfill & \hfill -6\hfill & \hfill -3\hfill \end{array}\right]& \hfill & \end{array}$

By the techniques of Chapter E we find the eigenvalues and eigenvectors,

$\begin{array}{llllllll}\hfill {\lambda }_1& =3& \hfill {\mathcal{ℰ}}_B\left(3\right)& =〈\left\{\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 1\hfill \\ \hfill -1\hfill \end{array}\right],\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -1\hfill \\ \hfill 1\hfill \\ \hfill 2\hfill \end{array}\right]\right\}〉& \hfill & & \hfill & \\ \hfill {\lambda }_2& =-2& \hfill {\mathcal{ℰ}}_B\left(-2\right)& =〈\left\{\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 2\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]\right\}〉& \hfill & & \hfill & \\ \hfill {\lambda }_3& =0& \hfill {\mathcal{ℰ}}_A\left(0\right)& =〈\left\{\left[\begin{array}{c}\hfill 2\hfill \\ \hfill -3\hfill \\ \hfill 2\hfill \\ \hfill 2\hfill \end{array}\right]\right\}〉& \hfill & & \hfill & \end{array}$

The algebraic and geometric multiplicities of each eigenvalue are equal, so Theorem DMFE tells us that $A$ is diagonalizable. With a single zero eigenvalue we see that $A$ has rank $4-1=3$ . Theorem DC says we can construct the nonsingular matrix $S$ with eigenvectors of $A$ as columns, so we have

$\begin{array}{llllllll}\hfill S& =\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 2\hfill \\ \hfill -2\hfill & \hfill -1\hfill & \hfill 2\hfill & \hfill -3\hfill \\ \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 2\hfill \\ \hfill -1\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill 2\hfill \end{array}\right]& \hfill S^{-1}& =\left[\begin{array}{cccc}\hfill 4\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill 8\hfill & \hfill 4\hfill & \hfill -1\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill -6\hfill & \hfill -3\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]& \hfill & & \hfill & \end{array}$

Since $r=3$ , we need only collect three vectors from each of these matrices,

$\begin{array}{llllllll}\hfill X& =\left\{\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 1\hfill \\ \hfill -1\hfill \end{array}\right],\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -1\hfill \\ \hfill 1\hfill \\ \hfill 2\hfill \end{array}\right],\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 2\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]\right\}& \hfill Y& =\left\{\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 2\hfill \\ \hfill 0\hfill \\ \hfill -1\hfill \end{array}\right],\left[\begin{array}{c}\hfill 8\hfill \\ \hfill 4\hfill \\ \hfill -1\hfill \\ \hfill -1\hfill \end{array}\right],\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 0\hfill \\ \hfill 1\hfill \\ \hfill 0\hfill \end{array}\right]\right\}& \hfill & & \hfill & \end{array}$

And we obtain the matrices,

$\begin{array}{llll}\hfill B_1& =3\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 1\hfill \\ \hfill -1\hfill \end{array}\right]{\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 2\hfill \\ \hfill 0\hfill \\ \hfill -1\hfill \end{array}\right]}^t=3\left[\begin{array}{cccc}\hfill 4\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -8\hfill & \hfill -4\hfill & \hfill 0\hfill & \hfill 2\hfill \\ \hfill 4\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -4\hfill & \hfill -2\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]=\left[\begin{array}{cccc}\hfill 12\hfill & \hfill 6\hfill & \hfill 0\hfill & \hfill -3\hfill \\ \hfill -24\hfill & \hfill -12\hfill & \hfill 0\hfill & \hfill 6\hfill \\ \hfill 12\hfill & \hfill 6\hfill & \hfill 0\hfill & \hfill -3\hfill \\ \hfill -12\hfill & \hfill -6\hfill & \hfill 0\hfill & \hfill 3\hfill \end{array}\right]& \hfill & \\ \hfill B_2& =3\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -1\hfill \\ \hfill 1\hfill \\ \hfill 2\hfill \end{array}\right]{\left[\begin{array}{c}\hfill 8\hfill \\ \hfill 4\hfill \\ \hfill -1\hfill \\ \hfill -1\hfill \end{array}\right]}^t=3\left[\begin{array}{cccc}\hfill 8\hfill & \hfill 4\hfill & \hfill -1\hfill & \hfill -1\hfill \\ \hfill -8\hfill & \hfill -4\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 8\hfill & \hfill 4\hfill & \hfill -1\hfill & \hfill -1\hfill \\ \hfill 16\hfill & \hfill 8\hfill & \hfill -2\hfill & \hfill -2\hfill \end{array}\right]=\left[\begin{array}{cccc}\hfill 24\hfill & \hfill 12\hfill & \hfill -3\hfill & \hfill -3\hfill \\ \hfill -24\hfill & \hfill -12\hfill & \hfill 3\hfill & \hfill 3\hfill \\ \hfill 24\hfill & \hfill 12\hfill & \hfill -3\hfill & \hfill -3\hfill \\ \hfill 48\hfill & \hfill 24\hfill & \hfill -6\hfill & \hfill -6\hfill \end{array}\right]& \hfill & \\ \hfill B_3& =\left(-2\right)\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 2\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]{\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 0\hfill \\ \hfill 1\hfill \\ \hfill 0\hfill \end{array}\right]}^t=\left(-2\right)\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill \\ \hfill -2\hfill & \hfill 0\hfill & \hfill 2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]=\left[\begin{array}{cccc}\hfill -2\hfill & \hfill 0\hfill & \hfill 2\hfill & \hfill 0\hfill \\ \hfill 4\hfill & \hfill 0\hfill & \hfill -4\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]& \hfill & \end{array}$

Then we verify that

$\begin{array}{llll}\hfill B& =B_1+B_2+B_3& \hfill & \\ \hfill & =\left[\begin{array}{cccc}\hfill 12\hfill & \hfill 6\hfill & \hfill 0\hfill & \hfill -3\hfill \\ \hfill -24\hfill & \hfill -12\hfill & \hfill 0\hfill & \hfill 6\hfill \\ \hfill 12\hfill & \hfill 6\hfill & \hfill 0\hfill & \hfill -3\hfill \\ \hfill -12\hfill & \hfill -6\hfill & \hfill 0\hfill & \hfill 3\hfill \end{array}\right]+\left[\begin{array}{cccc}\hfill 24\hfill & \hfill 12\hfill & \hfill -3\hfill & \hfill -3\hfill \\ \hfill -24\hfill & \hfill -12\hfill & \hfill 3\hfill & \hfill 3\hfill \\ \hfill 24\hfill & \hfill 12\hfill & \hfill -3\hfill & \hfill -3\hfill \\ \hfill 48\hfill & \hfill 24\hfill & \hfill -6\hfill & \hfill -6\hfill \end{array}\right]+\left[\begin{array}{cccc}\hfill -2\hfill & \hfill 0\hfill & \hfill 2\hfill & \hfill 0\hfill \\ \hfill 4\hfill & \hfill 0\hfill & \hfill -4\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]& \hfill & \\ \hfill & =\left[\begin{array}{cccc}\hfill 34\hfill & \hfill 18\hfill & \hfill -1\hfill & \hfill -6\hfill \\ \hfill -44\hfill & \hfill -24\hfill & \hfill -1\hfill & \hfill 9\hfill \\ \hfill 36\hfill & \hfill 18\hfill & \hfill -3\hfill & \hfill -6\hfill \\ \hfill 36\hfill & \hfill 18\hfill & \hfill -6\hfill & \hfill -3\hfill \end{array}\right]& \hfill & \end{array}$

$⊠$