2 Edited the title

# Efficient algorithm for a matrix porductproduct

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

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.

# Efficient algorithm for a matrix porduct

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.

# Efficient algorithm for a matrix product

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.

1

# Efficient algorithm for a matrix porduct

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.