Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
2 Edited the title
source | link

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.

    Tweeted twitter.com/StackSciComp/status/742015658838347776
1
source | link

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.