Multiplication of columns of matrix appended with identity matrix

matricessparse matrices

I have a matrix $A \in \mathbb{R}^{n\times n}$. Let $\{a_1,a_2,\ldots,a_n\}$ be its columns. I want to find the product of the matrices $A_1 \times A_2 \times\dots \times A_n$ where $A_i=[e_1 \quad e_2\quad \dots \quad a_i \quad \dots \quad e_n]$ and $e_i$ is the vector with all zeros elements except $i^{th}$ one which is $1$. Is there a standard formula or approach to solve such a problem which is faster than regular matrix multiplication ?

Does it help if we assume $A$ is sparse?

Best Answer

Note that $A_i = I + (a_i - e_i)e_i^T$, where $I$ denotes the $n \times n$ identity matrix. With that said, we can multiply by these matrices in a "recursive" fashion. Note that $$ M A_i = M(I + (a_i - e_i)e_i^T) = M + [M(a_i - e_i)]e_i^T. $$ The only column of $MA_i$ that is different from the corresponding column of $M$ is the $i$th. We find that $$ [M A_i]_i = [M + [M(a_i - e_i)]e_i^T]e_i = m_i + Ma_i - m_i = Ma_i. $$ In other words: at each step, it suffices to replace the $i$th column $m_i$ of $M$ with $Ma_i$.

To clarify what I mean, the corresponding Matlab code might look like this:

M = eye(n)
for i = 1:n
    M(:,i) = M * A(:,i);
end

The $M$ produced by this loop is the product $A_1 A_2 \cdots A_n$.

Related Question