Question

23. (Rank Factorization) Suppose an \[m \times n\] matrix A admits a factorization \[A = CD\] where C is \[m \times 4\] and D is \[4 \times n\].

1. Show that Ais the sum of four outer products. (See section 2.4.)
2. Let \[{\bf{m}} = {\bf{400}}\] and \[{\bf{n}} = {\bf{100}}\]. Explain why a computer programmer might prefer to store the data from A in the form of two matrices C and D.

Short answer

1. A can be written as the sum of four outer products.
2. Storing C and D together needs fewer entries than those required for A. Hence, a computer programmer might prefer to store the data from A in the form of two matrices C and D.

Step-by-step solution

Use the multiplication rule for partitioned matrices

(a)

Express each row of D as the transpose of a column vector.

\[D = \left[ {\begin{array}{*{20}{c}}{{d_1}^T}\\{{d_2}^T}\\{{d_3}^T}\\{{d_4}^T}\end{array}} \right]\]

Then,

\[\begin{array}{c}A = CD\\ = \left[ {\begin{array}{*{20}{c}}{{c_1}}&{{c_2}}&{{c_3}}&{{c_4}}\end{array}} \right]\left[ {\begin{array}{*{20}{c}}{{d_1}^T}\\{{d_2}^T}\\{{d_3}^T}\\{{d_4}^T}\end{array}} \right]\\A = {c_1}{d_1}^T + {c_2}{d_2}^T + {c_3}{d_3}^T + {c_4}{d_4}^T\end{array}\]

This implies that Ais the sum of four outer products.

Explain how a computer programmer works

(b)

Here, \[m = 400\] and \[n = 100\]. So, A has \[400 \times 100 = 40000\] entries. The matrices C with \[400 \times 4 = 1600\]entries and D with \[100 \times 4 = 400\] entries, hence, storing C and D together needs only 2000 entries, which is much smaller than 40000. So, the computer programmer needs only 2000 entries to store A directly.

Conclusion

Therefore, a computer programmer might prefer to store the data from A in the form of two matrices C and D.