Efficient algorithm for a matrix product

Question

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular column form matrix, $L_i$, is an elementary unit lower triangular matrix in which all of the nonzero subdiagonal elements are contained in a single column. For example, for $n = 4$

$$L_1 = \begin{pmatrix} 1 & 0 & 0 & 0\\ \lambda_{21} & 1 & 0 & 0\\ \lambda_{31} & 0 & 1 & 0\\ \lambda_{41} & 0 & 0 & 1\\ \end{pmatrix} \ \ \ L_2 = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & \lambda_{32} & 1 & 0\\ 0 & \lambda_{42} & 0 & 1\\ \end{pmatrix} \ \ \ L_3 = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & \lambda_{43} & 1\\ \end{pmatrix}$$

Our first task was to show that any unit lower triangular column form matrix, $L_i\in\mathbb{R}^{n\times n}$, can be written as the identity matrix plus an outer product of two vectors, i.e., $L_i = I + v_i w_i^{T}$ where $v_i\in\mathbb{R}^{n\times n}$ and $w_i\in \mathbb{R}^n$.

solution - Since only the $i$-th column of $L_i$ differs from the identity matrix the outer product $v_i w_i^{T}$ must have the same structure. This implies that $w_i = e_i$ and it follows that $v_i$ is added to the $i$-th column of $I$ to define $L_i e_i$. Since only elements below the main diagonal element are different from $I$, it follows that $v_i$ has a "lower" structure to its potentially nonzero elements. This is often indicated in the notation by using $l_i$ instead of the generic $v_i$. The conditions on the vector are $$l_i^{T}e_j = \begin{cases}0 \ & 1\leq j \leq i\\ \lambda_{ji} \ & i+1\leq j \leq n \end{cases}$$

and the expression is $L_i = I + l_i e_i^{T}$

Now the question I have is the following:

i.) Suppose $L_i\in\mathbb{R}^{n\times n}$ and $L_j\in\mathbb{R}^{n\times n}$ are elementary unit lower triangular column form matrices with $1\leq i < j \leq n-1$. Consider the matrix product $B = L_i L_j$. Determine an efficient algorithm to compute the product and its computational and storage complexity.

ii.) Suppose $L_i\in\mathbb{R}^{n\times n}$ and $L_j\in\mathbb{R}^{n\times n}$ are elementary unit lower triangular column form matrices with $1\leq j \leq i \leq n-1$. Consider the matrix product $B = L_i L_j$. Determine an efficient algorithm to compute the product and its computational and storage complexity.

The only difference from (i) and (ii) are the inequalities as you can see. I have been told that (i) requires no computation but I don't understand why. I am quite confused about these types of problems. Any suggestions are greatly appreciated.

Answer 1

A key to solving such problems is in the understanding of the definition of a matrix-matrix product. Without loss of generality, for square matrices $A,B\in\mathbb R^{n\times n}$, $C\in \mathbb R^{n\times n}, C=AB$ is defined as follows: $$ C=\left[ \begin{array}{cccc} \sum\limits_{k=1}^{n}a_{1k}b_{k1} & \sum\limits_{k=1}^{n}a_{1k}b_{k2} & \ldots & \sum\limits_{k=1}^{n}a_{1k}b_{kn}\\ \sum\limits_{k=1}^{n}a_{2k}b_{k1} & \sum\limits_{k=1}^{n}a_{2k}b_{k2} & \ldots & \sum\limits_{k=1}^{n}a_{2k}b_{kn}\\ \vdots & \vdots & \ddots & \vdots\\ \sum\limits_{k=1}^{n}a_{nk}b_{k1} & \sum\limits_{k=1}^{n}a_{nk}b_{k2} & \ldots & \sum\limits_{k=1}^{n}a_{nk}b_{kn}\\ \end{array} \right], \quad \text{or}\quad c_{vw}=\sum\limits_{k=1}^{n}a_{vk}b_{kw} $$ where $a_{vw}$ denotes the $(v,w)$th element of matrix $A$. Now, depending on the patterns\type\properties of $A$ and $B$, one can say a lot about the resultant product $C$.

For a particular case (ii) (sorry, some changes to your notation): $C=L^iL^j$, where $1\le i\le j<n$, ($L^i,L^j$ being lower triangular column-form matrices according to your definition):

$$ c_{vw}=\sum\limits_{k=1}^{n}\lambda^i_{vk}\lambda^j_{kw}= \begin{cases} 1,\quad v=w \quad(\text{product of lower-}\Delta\text{matrices})\\ 0,\quad w>v \quad(\text{product of lower-}\Delta\text{matrices})\\ \sum\limits_{k=1}^{n}\lambda^i_{vk}\lambda^j_{kw}=\lambda^i_{vw}\cdot 1+1\cdot\lambda^j_{vw}, \quad w<v \end{cases} $$ So, the resultant matrix $C$ is a lower triangular, where each ($v,w$)th entry under the main diagonal is a sum of $L^i$ and $L^j$ ($v,w$)th entries.

For example: $$ C=L^1 L^2=\left[ \begin{array}{cccccc} 1 & 0 & 0 &0 & \ldots & 0\\ \lambda^1_{21} & 1 & 0 & 0& \ldots & 0\\ \lambda^1_{31} & \lambda^2_{32} & 1 & 0 & \ldots & 0\\ \lambda^1_{41} & \lambda^2_{42} & 0 & 1 & \ldots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & 0 \\ \lambda^1_{n1} & \lambda^2_{n2} & 0 & 0 & \ldots & 1\\ \end{array} \right] $$

So, for case (i), when $i\neq j$, the resultant matrix $C$ can technically be named $L^{i,j}$, lower triangular two-column-form matrix, where all non-zero sub-diagonal elements are contained in columns $i$ and $j$ only. Computational complexity & memory (if only nnz are stored): $\mathcal O(n)$ if the result has to be written into a separate matrix storage (or overwritten in one of $A$, $B$) or nothing if an explicit copy is not required.

For case (ii), when $i\le j$, the computational complexity, and memory stays the same if a separate storage for $C$ is required. However, since $i$ can be equal to $j$, $i$th column of $C$ requires $\mathcal O(n)$ summations (1 per each subdiagonal element) anyway.

One can also derive exact flop count without Big-O notation by using $i$ and $j$.