Matrix factorization refers to the process of decomposing a larger matrix $A$ into the product of two smaller matrices $X$ and $Y$. This decomposition reduces the number of elements required to represent the original matrix. **Definition:** Consider a matrix $A$ with shape $(n \times m)$ and [[Matrix Rank]] $r$. This can be factorized as $ A=XY$ where: - $X$ is a $(n \times r)$ matrix - $Y$ is a $(r \times m)$ matrix ![[matrix-factorization.png|center|300]] While matrix $A$ has $(n*m)$ terms, the factorized version has only $(n*r)+(m*r)$ terms. When the rank $r$ is relatively small, this can lead to a significant decrease in matrix elements. ## Example Consider the following matrix: $ A= \begin{bmatrix} 1&2&3&5\\ 2&4&8&12\\ 3&6&7&13 \end{bmatrix} $ *Step1: Determine the Rank* The matrix $A$ has rank $2$, as only two of its columns are [[Linearly Independent Vectors|linearly independent]]. The first and third columns $C_1$ and $C_3$ can serve as [[Basis Vectors]] for the column space of $A$. *Step 2: Represent Columns as Linear Combinations* Express each column of $A$ as a linear combination of the basis vectors $C_1$ and $C_3$. $ \begin{align} C_1 = 1*C_1+0*C_3 \\ C_2 = 2*C_1+0*C_3 \\ C_3 = 0*C_1+1*C_3 \\ C_4 = 2*C_1+1*C_3 \end{align} $ *Step 3: Construct the Factorized Matrices* The columns of $X$ are formed from the basis vectors $C_1$ and $C_3$. $ X= \begin{bmatrix} 1&3\\ 2&8\\ 3&7 \end{bmatrix}$ The rows of $Y$ represent the coefficients of the linear combinations. $ Y= \begin{bmatrix} 1&2&0&2\\ 0&0&1&1 \end{bmatrix}$ *Step 4: Verify the Factorization* We see that the original matrix $A$ can be reconstructed by multiplying $X$ and $Y$. $ A=XY= \begin{bmatrix} 1&3\\ 2&8\\ 3&7 \end{bmatrix} \cdot \begin{bmatrix} 1&2&0&2\\ 0&0&1&1 \end{bmatrix} = \begin{bmatrix} 1&2&3&5\\ 2&4&8&12\\ 3&6&7&13 \end{bmatrix} $