Note: This is a follow-up to my previous post “Outer Products: The Dual View of Linear Algebra”. It might be worth checking that post out if you’d like more of a background on what outer products are, and why I think they’re neat.

Let’s say you’re under pressure to do some quick math – maybe to save the world from some doomsday plot or villain – and in order to defeat this villain you need to decompose some arbitrary matrix $\mathbf{W}$ you are handed into a sum of outer products. Luckily for you, you read this blog post just last week, and you know that there are two trivial decomposition of any matrix into a sum of outer products.

You already know that any matrix multiplication between two matrices can be rewritten as a sum over the outer product of the columns of the left matrix (denoted $\bm{a}_i^{\text{col}}$) with the rows of the right matrix (denoted $\bm{b}_i^{\text{row}}$):

\[\mathbf{C} = \mathbf{AB} = \begin{bmatrix} \bm{a}_1^{\text{col}} & \cdots & \bm{a}_p^{\text{col}} \end{bmatrix} \begin{bmatrix} \bm{b}_1^{\text{row}} \\ \vdots \\ \bm{b}_p^{\text{row}} \end{bmatrix} = \sum_{k = 1}^p \bm{a}_k^{\text{col}} \otimes [\bm{b}_k^{\text{row}}]^\top\]

While this doesn’t immediately tell you how to decompose a single matrix into outer products, there is one simple trick we can use to apply that result. The trick is multiplying (on either side) the identity matrix. So, for any $n$ by $m$ matrix $\mathbf{W}$, two answers to whatever weird riddle you’ve been given in this scenario are:

\[\mathbf{W}\mathcal{I} = \begin{bmatrix} \bm{w}_1^{\text{col}} & \cdots & \bm{w}_m^{\text{col}} \end{bmatrix} \begin{bmatrix} \bm{e}_1^{\text{row}} \\ \vdots \\ \bm{e}_m^{\text{row}} \end{bmatrix} = \sum_{k = 1}^m \bm{w}_k^{\text{col}} \otimes [\bm{e}_k^{\text{row}}]^\top\]

and

\[\mathcal{I}\mathbf{W} = \begin{bmatrix} \bm{e}_1^{\text{col}} & \cdots & \bm{e}_n^{\text{col}} \end{bmatrix} \begin{bmatrix} \bm{w}_1^{\text{row}} \\ \vdots \\ \bm{w}_n^{\text{row}} \end{bmatrix} = \sum_{k = 1}^n \bm{e}_k^{\text{col}} \otimes [\bm{w}_k^{\text{row}}]^\top\]

Where $\bm{e}_i$ is the $i$th row or column of the identity matrix $\mathcal{I}$.

One way of framing what this trivial decomposition does is it “paints in” the matrix $\mathbf{W}$ row-wise or column wise. Recalling the following visual from my previous post (pasted below), taking the outer product with the identity matrix row/column “paints in” whatever the other vector is into the resulting matrix.

$$ x \otimes y = \begin{bmatrix} \color{green} x_1 \\ \color{red} x_2 \\ \vdots \\ \color{blue} x_n \end{bmatrix} \begin{bmatrix} y_1 & y_2 & \cdots & y_n \end{bmatrix} = \begin{bmatrix} {\color{green} x_1} y_1 & {\color{green} x_1} y_2 & \cdots & {\color{green} x_1} y_n \\ {\color{red} x_2} y_1 & {\color{red} x_2} y_2 & \cdots & {\color{red} x_2} y_2 \\ \vdots & \vdots & \ddots & \vdots \\ {\color{blue} x_n} y_1 & {\color{blue} x_n} y_2 & \cdots & {\color{blue} x_n} y_n \end{bmatrix} $$

If $x$ (above) is replaced with the vector from the identity matrix, then each term of the summation is adding one row to our matrix $\mathbf{W}$. If $y$ is replaced with the vector from the identity matrix instead, then each term of the summation is adding one column to our matrix.

Neat!