4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this homework? If so, you should tag it as such. $\endgroup$ – Bill Barth Jun 9 '16 at 18:19
  • 1
    $\begingroup$ @BillBarth It was Homework but I am preparing for the qualifying exam in August. If you think its relevant to tag as homework I will do it $\endgroup$ – Wolfy Jun 9 '16 at 18:22
  • 1
    $\begingroup$ Wolfy, we don't appear to have an "exam-question" tag. So, maybe? Did you not get an answer at the time? Does your department not have a binder of such qual questions and answers floating around among grad students. Mine did, though I never saw it nor contributed to it. $\endgroup$ – Bill Barth Jun 9 '16 at 18:26
  • $\begingroup$ @BillBarth I asked my professor but he does not provide qual questions or answers unfortunately which is probably why no one passed his Quals last summer haha $\endgroup$ – Wolfy Jun 9 '16 at 18:28
  • $\begingroup$ There was a semi-secret binder of qual questions with good answers floating around my department kept by the students. $\endgroup$ – Bill Barth Jun 9 '16 at 18:34
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.