Given Triangular Form of Matrix Find Solution

Linear Equations

William Ford , in Numerical Linear Algebra with Applications, 2015

2.3.1 Upper-Triangular Form

In upper-triangular form, a simple procedure known as back substitution determines the solution. Since the linear algebraic systems corresponding to the original and final augmented matrix have the same solution, the solution to the upper-triangular system

$\left[\begin{array}{llll}{c}_{11}\hfill & c_{12}\hfill & \dots \hfill & c_{1n}\hfill \\ 0\hfill & c_{22}\hfill & \dots \hfill & c_{2n}\hfill \\ ⋮\hfill & ⋮\hfill & \ddots \hfill & ⋮\hfill \\ 0\hfill & \dots \hfill & c_{n-1,n-1}\hfill & c_{n-1,n}\hfill \\ 0\hfill & 0\hfill & \dots \hfill & c_n\hfill \end{array}\left|\begin{array}{l}{b}_1^{\prime }\hfill \\ b_2^{\prime }\hfill \\ ⋮\hfill \\ b_{n-1}^{\prime }\hfill \\ b_n^{\prime }\hfill \end{array}\right.\right]$

begins with

$x_n=\frac{b_n^{\prime }}{c_{\mathit{nn}}}$

followed by

${x_n}_{-1}=\frac{b_{n-1}^{\prime }-{c_n}_{-1,n}{x}_n}{{c_n}_{-1,n-1}}\text{.}$

In general,

$x_i=\frac{b_i^{\prime }-{\displaystyle {\sum }_{j=i+1}^n{c}_{\mathit{ij}}{x}_j}}{c_{\mathit{ii}}},i=n-1,n-2,\dots ,1\text{.}$

We now formally describe the Gaussian elimination procedure. Start with matrix A and produce matrix B in upper-triangular form which is row-equivalent to A. If A is the augmented matrix of a system of linear equations, then applying back substitution to B determines the solution to the system. It is also possible that there is no solution to the system, and the row-reduction process will make this evident.

Begin at element a ₁₁. If a ₁₁  =   0, exchange rows so a ₁₁  ≠   0. Now make all the elements below a ₁₁ zero by subtracting a multiple of row 1 from row i, 2   ≤ i  ≤ n. The multiplier used for row i is

$\frac{{a_i}_1}{a_{11}}\text{.}$

The matrix is now in this form

$\left[\begin{array}{llll}{a}_{11}\hfill & a_{12}\hfill & \dots \hfill & a_{1n}\hfill \\ 0\hfill & a_{22}^{\prime }\hfill & \dots \hfill & a_{2n}^{\prime }\hfill \\ ⋮\hfill & ⋮\hfill & \ddots \hfill & ⋮\hfill \\ 0\hfill & a_{n2}^{\prime }\hfill & \dots \hfill & a_{\mathit{nn}}^{\prime }\hfill \end{array}\left|\begin{array}{c}\hfill b_1\hfill \\ \hfill b_2^{\prime }\hfill \\ \hfill ⋮\hfill \\ \hfill b_n^{\prime }\hfill \end{array}\right.\right]\text{.}$

Now perform the same process of elimination by using $a_{22}^{\prime }$ and multipliers ${a_i^{\prime }}_2/a_{22}^{\prime }$ , making a row exchange if necessary, so that all the elements below $a_{22}^{\prime }$ are 0,

$\left[\begin{array}{lllll}{a}_{11}\hfill & a_{12}\hfill & \dots \hfill & \dots \hfill & a_{1n}\hfill \\ 0\hfill & a_{22}^{\prime }\hfill & \dots \hfill & \dots \hfill & a_{2n}^{\prime }\hfill \\ ⋮\hfill & 0\hfill & a_{33}^{″}\hfill & ⋮\hfill & a_{3n}^{″}\hfill \\ 0\hfill & 0\hfill & a_{43}^{″}\hfill & \ddots \hfill & a_{4n}^{″}\hfill \\ ⋮\hfill & ⋮\hfill & ⋮\hfill & \ddots \hfill & ⋮\hfill \\ 0\hfill & 0\hfill & a_{n3}^{″}\hfill & \dots \hfill & a_{\mathit{nn}}^{″}\hfill \end{array}\left|\begin{array}{l}{b}_1\hfill \\ b_2^{\prime }\hfill \\ b_3^{\prime }\hfill \\ b_4^{\prime }\hfill \\ ⋮\hfill \\ b_n^{\prime }\hfill \end{array}\right.\right]$

Repeat this process until the matrix is in upper-triangular form, and then execute back substitution to compute the solution.

Example 2.4

Solve the system

$\begin{array}{l}{x}_1+x_2-x_3=1,\\ 2x_1+x_2+x_3=0,\\ -x_1-2x_2+3x_3=2\text{.}\end{array}$

Row reduce the augmented matrix to upper-triangular form.

$\begin{array}{l}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill -2\hfill & \hfill 3\hfill \end{array}\left|\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \\ \hfill 2\hfill \end{array}\right.\right]\overrightarrow{R_2=R_2-2R_1}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 3\hfill \\ \hfill -1\hfill & \hfill -2\hfill & \hfill 3\hfill \end{array}\left|\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 2\hfill \end{array}\right.\right]\\ \left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 3\hfill \\ \hfill -1\hfill & \hfill -2\hfill & \hfill 3\hfill \end{array}\left|\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 2\hfill \end{array}\right.\right]\overrightarrow{R_3=R_3-\left(-1\right)R_1}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 3\hfill \\ \hfill -1\hfill & \hfill -2\hfill & \hfill 2\hfill \end{array}\left|\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 3\hfill \end{array}\right.\right]\\ \left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 3\hfill \\ \hfill -1\hfill & \hfill -2\hfill & \hfill 3\hfill \end{array}\left|\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 2\hfill \end{array}\right.\right]\overrightarrow{R_3=R_3-\left(-1\right)R_2}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 3\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 2\hfill \end{array}\left|\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 5\hfill \end{array}\right.\right]\end{array}$

Execute back substitution.

$\begin{array}{l}\left(-1\right)x_3=5,x_3=-5,\\ -x_2+3\left(-5\right)=-2,x_2=-13,\\ x_1+\left(1\right)\left(-13\right)-\left(-5\right)=1,x_1=9\text{.}\end{array}$

Final solution: x ₁  =   9, x ₂  =   −   13, x ₃  =   −   5

When computing a solution "by hand," it is a good idea to verify that the solution is correct.

$\begin{array}{l}9+\left(-13\right)-\left(-5\right)=1,\\ 2\left(9\right)+\left(-13\right)+\left(-5\right)=0,\\ -\left(9\right)-2\left(-13\right)+3\left(-5\right)=2\text{.}\end{array}$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123944351000028

The inverse

Richard Bronson , Gabriel B. Costa , in Matrix Methods (Fourth Edition), 2021

3.5 LU decomposition

Matrix inversion of elementary matrices (see Section 3.1) can be combined with the third elementary row operation (see Section 2.3) to generate a good numerical technique for solving simultaneous equations. It rests on being able to decompose a nonsingular square matrix A into the product of lower triangular matrix L with an upper triangular matrix U. Generally, there are many such factorizations. If, however, we add the additional condition that all diagonal elements of L be unity, then the decomposition, when it exists, is unique, and we may write

(7) $\mathbf{A}=\mathbf{L}\mathbf{U}$

with

$\mathbf{L}=\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ l_{21}& 1& 0& \cdots & 0\\ l_{31}& l_{32}& 1& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ l_{n1}& l_{n2}& l_{n3}& \cdots & 1\end{array}\right]$

and

$\mathbf{U}=\left[\begin{array}{ccccc}{u}_{11}& u_{12}& u_{13}& \cdots & u_{1n}\\ 0& u_{22}& u_{23}& \cdots & u_{2n}\\ 0& 0& u_{33}& \cdots & u_{3n}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & u_{nn}\end{array}\right]\text{.}$

To decompose A into from (7), we first reduce A to upper triangular form using just the third elementary row operation: namely, add to one row of a matrix a scalar times another row of that same matrix. This is completely analogous to transforming a matrix to row-reduced form, except that we no longer use the first two elementary row operations. We do not interchange rows and we do not multiply a row by a nonzero constant. Consequently, we no longer require the first nonzero element of each nonzero row to be unity, and if any of the pivots are zero—which in the row-reduction scheme would require a row interchange operation—then the decomposition scheme we seek cannot be done.

Example 1

Use the third elementary row operation to transform the matrix

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]$

into upper triangular form.

Solution

$\begin{array}{llll}\mathbf{A}=\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]\hfill & \to \hfill & \left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{second}\text{row}\left(-2\right)\text{times}\\ \text{the}\text{first}\text{row}\end{array}\hfill \\ \hfill & \to \hfill & \left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill -4& \hfill 11\end{array}\right]\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{third}\text{row}\left(3\right)\text{times}\\ \text{the}\text{first}\text{row}\end{array}\hfill \\ \hfill & \to \hfill & \left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right]\text{.}\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{third}\text{row}\left(1\right)\text{times}\\ \text{the}\text{second}\text{row}\end{array}■\hfill \end{array}$

If a square matrix A can be reduced to upper triangular form U by a sequence of elementary row operations of the third type, then there exists a sequence of elementary matrices E ₂₁, E ₃₁, E ₄₁, …, E _{n, n−1} such that

(8) $\left({\mathbf{E}}_{n-1,n}\cdots {\mathbf{E}}_{41}{\mathbf{E}}_{31}{\mathbf{E}}_{21}\right)\mathbf{A}=\mathbf{U},$

where E ₂₁ denotes the elementary matrix that places a zero in the 2−1 position, E ₃₁ denotes the elementary matrix that places a zero in the 3−1 position, E ₄₁ denotes the elementary matrix that places a zero in the 4−1 position, and so on. Since elementary matrices have inverses, we can write (8) as

(9) $\mathbf{A}=\left({\mathbf{E}}_{21}^{-1}{\mathbf{E}}_{31}^{-1}{\mathbf{E}}_{41}^{-1}\cdots {\mathbf{E}}_{n,n-1}^{-1}\right)\mathbf{U}\text{.}$

Each elementary matrix in (8) is lower triangular. It follows from Property 7 of Section 3.4 that each of the inverses in (9) are lower triangular and then from Theorem 1 of Section 1.4 that the product of these lower triangular matrices is itself lower triangular. Setting

$\mathbf{L}={\mathbf{E}}_{21}^{-1}{\mathbf{E}}_{31}^{-1}{\mathbf{E}}_{41}^{-1}\cdots {\mathbf{E}}_{n,n-1}^{-1},$

we see that (9) is identical to (7), and we have the decomposition we seek.

Example 2

Construct an LU decomposition for the matrix given in Example 1.

Solution The elementary matrices associated with the elementary row operations described in Example 1 are

$\begin{array}{rrrr}\hfill {\mathbf{E}}_{21}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill -2& \hfill 1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right],& \hfill {\mathbf{E}}_{31}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill 3& \hfill 0& \hfill 1\end{array}\right],& \hfill \mathrm{and}& \hfill {\mathbf{E}}_{42}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill 1& \hfill 1\end{array}\right],\end{array}$

with inverses given respectively by

$\begin{array}{rrrr}\hfill {\mathbf{E}}_{21}^{-1}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right],& \hfill {\mathbf{E}}_{31}^{-1}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill -3& \hfill 0& \hfill 1\end{array}\right],& \hfill \mathrm{and}& \hfill {\mathbf{E}}_{42}^{-1}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill -1& \hfill 1\end{array}\right].\end{array}$

Then,

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill -3& \hfill 0& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill -1& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right]$

or, upon multiplying together the inverses of the elementary matrices,

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill -3& \hfill -1& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right]\text{.}■$

Example 2 suggests an important simplification of the decomposition process. Note the elements in L below the main diagonal are the negatives of the scalars used in the elementary row operations to reduce the original matrix to upper triangular form! This is no coincidence. In general

Observation 1

If an elementary row operation is used to put a zero in the i−j position of A(i  > j) by adding to row i a scalar k times row j, then the i−j element of L in the LU decomposition of A is −k.

We summarize the decomposition process as follows: Use only the third elementary row operation to transform a given square matrix A to upper triangular form. If this is not possible, because of a zero pivot, then stop; otherwise, the LU decomposition is found by defining the resulting upper triangular matrix as U and constructing the lower triangular matrix L utilizing Observation 1.

Example 3

Construct an LU decomposition for the matrix

$\mathbf{A}=\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 6& \hfill 2& \hfill 4& \hfill 8\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]\text{.}$

Solution Transforming A to upper triangular form, we get

$\begin{array}{llll}\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 6& \hfill 2& \hfill 4& \hfill 8\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]\hfill & \to \hfill & \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{second}\text{row}\left(-3\right)\text{times}\\ \text{the}\text{first}\text{row}\end{array}\hfill \\ \hfill & \to \hfill & \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill -\frac{3}{2}& \hfill -1& \hfill \frac{5}{2}\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{third}\text{row}\left(-\frac{1}{2}\right)\text{times}\\ \text{the}\text{first}\text{row}\end{array}\hfill \\ \hfill & \to \hfill & \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{third}\text{row}\left(-\frac{3}{2}\right)\text{times}\\ \text{the}\text{second}\text{row}\end{array}\hfill \\ \hfill & \to \hfill & \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 0& \hfill -5& \hfill -5\end{array}\right]\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{fourth}\text{row}\left(1\right)\text{times}\\ \text{the}\text{second}\text{row}\end{array}\hfill \\ \hfill & \to \hfill & \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 0& \hfill 0& \hfill 5\end{array}\right].\hfill & \{\begin{array}{l}\text{by}\text{adding}\text{to}\text{the}\\ \text{fourth}\text{row}\left(\frac{5}{2}\right)\text{times}\\ \text{the}\text{third}\text{row}\end{array}\hfill \end{array}$

We now have an upper triangular matrix U. To get the lower triangular matrix L in the decomposition, we note that we used the scalar −3 to place a zero in the 2−1 position, so its negative −(−3)   =   3 goes into the 2−1 position of L. We used the scalar $-\frac{1}{2}$ to place a zero in the 3−1 position in the second step of the above triangularization process, so its negative, $\frac{1}{2}$ , becomes the 3−1 element in L; we used the scalar $\frac{5}{2}$ to place a zero in the 4−3 position during the last step of the triangularization process, so its negative, $-\frac{5}{\mathrm{2,}}$ becomes the 4−3 element in L. Continuing in this manner, we generate the decomposition

$\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 6& \hfill 2& \hfill 4& \hfill 8\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]=\left[\begin{array}{rrrr}\hfill 1& \hfill 0& \hfill 0& \hfill 0\\ \hfill 3& \hfill 1& \hfill 0& \hfill 0\\ \hfill \frac{1}{2}& \hfill \frac{3}{2}& \hfill 1& \hfill 0\\ \hfill 0& \hfill -1& \hfill -\frac{5}{2}& \hfill 1\end{array}\right]\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 0& \hfill 0& \hfill 5\end{array}\right]\text{.}■$

LU decompositions, when they exist, can be used to solve systems of simultaneous linear equations. If a square matrix A can be factored into A  = LU, then the system of equations Ax  = b can be written as L(Ux)   = b. To find x, we first solve the system

(10) $\mathbf{L}\mathbf{y}=\mathbf{b}$

for y, and then, once y is determined, we solve the system

(11) $\mathbf{U}\mathbf{x}=\mathbf{y}$

for x. Both systems (10) and (11) are easy to solve, the first by forward substitution and the second by backward substitution.

Example 4

Solve the system of equations

$\begin{array}{ll}\begin{array}{r}\hfill 2x-y+3z=\\ \hfill 4x+2y+z=\\ \hfill -6x-y+2z=\end{array}\hfill & \begin{array}{r}\hfill 9,\\ \hfill 9,\\ \hfill 12.\end{array}\hfill \end{array}$

Solution This system has the matrix form

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]\left[\begin{array}{r}\hfill x\\ \hfill y\\ \hfill z\end{array}\right]=\left[\begin{array}{r}\hfill 9\\ \hfill 9\\ \hfill 12\end{array}\right]\text{.}$

The LU decomposition for the coefficient matrix A is given in Example 2. If we define the components of y by α, β, and γ, respectively, the matrix system Ly   =   b is

$\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill -3& \hfill -1& \hfill 1\end{array}\right]\left[\begin{array}{r}\hfill \alpha \\ \hfill \beta \\ \hfill \gamma \end{array}\right]=\left[\begin{array}{r}\hfill 9\\ \hfill 9\\ \hfill 12\end{array}\right],$

which is equivalent to the system of equations

$\begin{array}{lll}\begin{array}{l}\alpha \hfill \\ 2\alpha +\beta \hfill \\ -3\alpha -\beta +\gamma \hfill \end{array}\hfill & \begin{array}{c}=\\ =\\ =\end{array}\hfill & \begin{array}{r}\hfill 9,\\ \hfill 9,\\ \hfill 12.\end{array}\hfill \end{array}$

Solving this system from top to bottom, we get α  =   9, β  =   −9, and γ  =   30. Consequently, the matrix system Ux  = y is

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right]\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=\left[\begin{array}{r}\hfill 9\\ \hfill -9\\ \hfill 30\end{array}\right].$

which is equivalent to the system of equations

$\begin{array}{ll}\begin{array}{l}2x-y+3z=\hfill \\ 4y-5z=\hfill \\ 6z=\hfill \end{array}\hfill & \begin{array}{r}\hfill 9,\\ \hfill -9,\\ \hfill 30.\end{array}\hfill \end{array}$

Solving this system from bottom to top, we obtain the final solution x  =   −1, y  =   4, and z  =   5. ■

Example 5

Solve the system

$\begin{array}{r}\hfill 2a+b+2c+3d=5,\\ \hfill 6a+2b+4c+8d=8,\\ \hfill a-b+4d=-4,\\ \hfill b-3c-4d=-3.\end{array}$

Solution The matrix representation for this system has as its coefficient matrix the matrix A of Example 3. Define

$\mathbf{y}={\left[\alpha ,\beta ,\gamma ,\delta \right]}^{\text{T}}\text{.}$

Then, using the decomposition determined in Example 3, we can write the matrix system Ly  = b as the system of equations

$\begin{array}{c}\alpha =5,\\ 3\alpha +\beta =8,\\ \frac{1}{2}\alpha +\frac{3}{2}\beta +\gamma =-4,\\ -\beta -\frac{5}{2}\gamma +\delta =-3,\end{array}$

which has as its solution α  =   5, β  =   −7, γ  =   4, and δ  =   0. Thus, the matrix system Ux  = y is equivalent to the system of equations

$\begin{array}{lll}\begin{array}{r}\hfill 2a+b+2c+3d\\ \hfill -b-2c-d\\ \hfill 2c+4d\\ \hfill 5d\end{array}\hfill & \begin{array}{c}=\\ =\\ =\\ =\end{array}\hfill & \begin{array}{r}\hfill 5,\\ \hfill -7,\\ \hfill 4,\\ \hfill 0.\end{array}\hfill \end{array}$

Solving this set from bottom to top, we calculate the final solution a  =   −1, b  = 3, c  =   2, and d  =   0. ■

LU decomposition and Gaussian elimination are equally efficient for solving Ax  = b, when the decomposition exists. LU decomposition is superior when Ax  = b must be solved repeatedly for different values of b but the same A, because once the factorization of A is determined it can be used with all b. (See Problems 17 and 18.) A disadvantage of LU decomposition is that it does not exist for all nonsingular matrices, in particular whenever a pivot is zero. Fortunately, this occurs rarely and when it does the difficulty usually overcome by simply rearranging the order of the equations. (See Problems 19 and 20.)

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128184196000034

Determinants and Eigenvalues

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fourth Edition), 2010

Calculating the Determinant by Row Reduction

We will now illustrate how to use row operations to calculate the determinant of a given matrix A by finding an upper triangular matrix B that is row equivalent to A.

Example 4

Let

$A=\left[\begin{array}{ccc}0& -14& -8\\ 1& 3& 2\\ -2& 0& 6\end{array}\right].$

We row reduce A to upper triangular form, as follows, keeping track of the effect on the determinant at each step:

$A=\left[\begin{array}{ccc}0& -14& -8\\ 1& 3& 2\\ -2& 0& 6\end{array}\right]$

$\left(\text{III}\right):〈1〉\leftrightarrow 〈2〉\Rightarrow B_1=\left[\begin{array}{ccc}1& 3& 2\\ 0& -14& -8\\ -2& 0& 6\end{array}\right]\left(\left|B_1\right|=-\left|A\right|\right)$

$\left(\text{II}\right)\text{:}〈3〉\leftarrow 2〈1〉+〈3〉\Rightarrow B_2=\left[\begin{array}{ccc}1& 3& 2\\ 0& -14& -8\\ 0& 6& 10\end{array}\right]\left(\left|B_2\right|=\left|B_1\right|=-\left|A\right|\right)$

$\left(\text{I}\right)\text{:}〈2〉\leftarrow -\frac{1}{14}〈2〉\Rightarrow B_3=\left[\begin{array}{ccc}1& 3& 2\\ 0& 1& \frac{4}{7}\\ 0& 6& 10\end{array}\right]\left(\left|B_3\right|=-\frac{1}{14}\left|B_2\right|=+\frac{1}{14}\left|A\right|\right)$

Because the last matrix B is in upper triangular form, we stop. (Notice that we do not target the entries above the main diagonal, as in reduced row echelon form.) From Theorem 3.2, $\left|B\right|=(1)(1)\left(\frac{46}{7}\right)=\frac{46}{7}.$ Since $\left|B\right|=+\frac{1}{14}\left|A\right|$ , we see that $\left|A\right|=14\left|B\right|=14(\frac{46}{7})=92$ .

A more convenient method of calculating |A| is to create a variable P (for "product") with initial value 1, and update P appropriately as each row operation is performed. That is, we replace the current value of P by

$\{\begin{array}{ll}P\times c\hfill & \text{for\hspace{0.17em}type\hspace{0.17em}(I)\hspace{0.17em}row\hspace{0.17em}operations}\hfill \\ P\times (-1)\hfill & \text{for\hspace{0.17em}type\hspace{0.17em}(III)\hspace{0.17em}row\hspace{0.17em}operations}\hfill \end{array}.$

Of course, row operations of type (II) do not affect the determinant. Then, using the final value of P, we can solve for |A| using |B| = P|A|, where B is the upper triangular result of the row reduction process. This method is illustrated in the next example.

Example 5

Let us redo the calculation for |A| in Example 4. We create a variable P and initialize P to 1. Listed below are the row operations used in that example to convert A into upper triangular form B, with $\left|B\right|=\frac{46}{7}$ . After each operation, we update the value of P accordingly.

Row Operation	Effect	P
$(\text{III}):〈1〉\leftrightarrow 〈2〉$	Multiply P by −1	−1
$(\text{II}):〈3〉\leftarrow 2〈1〉+〈3〉$	No change	−1
$(\text{I}):〈2〉\leftarrow -\frac{1}{14}〈2〉$	Multiply P by $-\frac{1}{14}$	$\frac{1}{14}$
$(\text{II}):〈3〉\leftarrow -6〈2〉+〈3〉$	No change	$\frac{1}{14}$

Then |A| equals the reciprocal of the final value of P times |B| that is, $\left|A\right|=(1/P)\left|B\right|=14\times \frac{46}{7}=92$ .

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747518000226

Conditioning of Problems and Stability of Algorithms

William Ford , in Numerical Linear Algebra with Applications, 2015

Reasons Why the Study of Numerical Linear Algebra Is Necessary

Floating point roundoff and truncation error cause many problems. We have learned how to perform Gaussian elimination in order to row reduce a matrix to upper-triangular form. Unfortunately, if the pivot element is small, this can lead to serious errors in the solution. We will solve this problem in Chapter 11 by using partial pivoting. Sometimes an algorithm is simply far too slow, and Cramer's Rule is an excellent example. It is useful for theoretical purposes but, as a method of solving a linear system, should not be used for systems greater than 2   ×   2. Solving Ax  = b by finding A ^{−   1} and then computing x  = A ^{−   1} b is a poor approach. If the solution to a single system is required, one step of Gaussian elimination, properly performed, requires far fewer flops and results in less roundoff error. Even if the solution is required for many right-hand sides, we will show in Chapter 11 that first factoring A into a product of a lower- and an upper-triangular matrix and then performing forward and back substitution is much more effective. A classical mistake is to compute eigenvalues by finding the roots of the characteristic polynomial. Polynomial root finding can be very sensitive to roundoff error and give extraordinarily poor results. There are excellent algorithms for computing eigenvalues that we will study in Chapters 18 and 19. Singular values should not be found by computing the eigenvalues of A ^T A. There are excellent algorithms for that purpose that are not subject to as much roundoff error. Lastly, if m   ≠   n a theoretical linear algebra course deals with the system using a reduction to what is called reduced row echelon form. This will tell you whether the system has infinitely many solutions or no solution. These types of systems occur in least-squares problems, and we want a single meaningful solution. We will find one by requiring that x be such that ‖b  − Ax‖₂ is minimum.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123944351000107

Matrix Representation of Linear Algebraic Equations

Stormy Attaway , in Matlab (Second Edition), 2012

Gauss elimination

The Gauss elimination method consists of:

▪

creating the augmented matrix [A|b]

▪

applying EROs to this augmented matrix to get an upper triangular form (this is called forward elimination )

▪

back substitution to solve

For example, for a 2 × 2 system, the augmented matrix would be:

$\left[\begin{array}{ccc}{a}_{11}& a_{12}& b_1\\ a_{21}& a_{22}& b_2\end{array}\right]$

Then, elementary row operations are applied to get the augmented matrix into an upper triangular form (i.e., the square part of the matrix on the left is in upper triangular form):

$\left[\begin{array}{ccc}{a}_{11}^{\prime }& a_{12}^{\prime }& b_1^{\prime }\\ 0& a_{22}^{\prime }& b_2^{\prime }\end{array}\right]$

So, the goal is simply to replace a ₂₁ with 0. Here, the primes indicate that the values (may) have been changed.

Putting this back into the equation form yields

$\left[\begin{array}{cc}{a}_{11}^{\prime }& a_{12}^{\prime }\\ 0& a_{22}^{\prime }\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}{b}_1^{\prime }\\ b_2^{\prime }\end{array}\right]$

Performing this matrix multiplication for each row results in:

a′₁₁ x₁ + a′₁₂ x₂ = b′₁

a′₂₂ x₂ = b′₂

So, the solution is

x₂ = b′₂ / a′₂₂

x₁ = (b′₁ − a′₁₂ x₂) / a′₁₁

Similarly, for a 3 × 3 system, the augmented matrix is reduced to upper triangular form:

$\left[\begin{array}{c}\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& b_1\end{array}\\ \begin{array}{cccc}{a}_{21}& a_{22}& a_{23}& b_2\end{array}\\ \begin{array}{cccc}{a}_{31}& a_{32}& a_{33}& b_3\end{array}\end{array}\right]\to \left[\begin{array}{cccc}{a}_{11}^{\prime }& a_{12}^{\prime }& a_{13}^{\prime }& b_1^{\prime }\\ 0& a_{22}^{\prime }& a_{23}^{\prime }& b_2^{\prime }\\ 0& 0& a_{33}^{\prime }& b_3^{\prime }\end{array}\right]$

(This will be done systematically by first getting a 0 in the a ₂₁ position, then a ₃₁, and finally a ₃₂.) Then, the solution will be:

x₃ = b₃′ / a₃₃′

x₂ = (b₂′ − a₂₃′x₃) / a₂₂′

x₁ = (b₁′ − a₁₃′_x3 − a₁₂′x₂) / a₁₁′

Note that we find the last unknown, x₃, first, then the second unknown, and then the first unknown. This is why it is called back substitution.

As an example, consider the following 2 × 2 system of equations:

x₁ + 2x₂ = 2

2x₁ + 2x₂ = 6

As a matrix equation Ax = b, this is:

$\left[\begin{array}{cc}1& 2\\ 2& 2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}2\\ 6\end{array}\right]$

The first step is to augment the coefficient matrix A with b to get an augmented matrix [A|b]:

$\left[\begin{array}{ccc}1& 2& 2\\ 2& 2& 6\end{array}\right]$

For forward elimination, we want to get a 0 in the a ₂₁ position. To accomplish this, we can modify the second line in the matrix by subtracting from it 2 * the first row.

The way we would write this ERO follows:

$\left[\begin{array}{ccc}1& 2& 2\\ 2& 2& 6\end{array}\right]{\text{r}}_2-2{\text{r}}_1\to {\text{r}}_2\left[\begin{array}{ccc}1& 2& 2\\ 0& -2& 2\end{array}\right]$

Now, putting it back in matrix equation form:

$\left[\begin{array}{cc}1& 2\\ 0& -2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}2\\ 2\end{array}\right]$

says that the second equation is now −2x₂ = 2, so x₂ = −1. Plugging into the first equation,

${\text{x}}_1{+2(-1)=2,\text{so}\text{x}}_1=4$

This is back substitution.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123850812000120

Vectors and Matrices

Frank E. Harris , in Mathematics for Physical Science and Engineering, 2014

Exercises

For each of the following equation sets:

(a)

Compute the determinant of the coefficients, using Eq. (4.61).

(b)

Row-reduce the coefficient matrix to upper triangular form and either obtain the most general solution to the equations or explain why no solution exists.

(c)

Confirm that the existence and/or uniqueness of the solutions you found in part (b) correspond to the zero (or nonzero) value you found for the determinant.

4.6.1

$\begin{array}{cc}\hfill & x-y+2z=5\text{,}\hfill \\ \hfill & 2x+z=3\text{,}\hfill \\ \hfill & x+3y-z=-6\text{.}\hfill \end{array}$

4.6.2

$\begin{array}{cc}\hfill & 2x+4y+3z=4\text{,}\hfill \\ \hfill & 3x+y+2z=3\text{,}\hfill \\ \hfill & 4x-2y+z=2\text{.}\hfill \end{array}$

4.6.3

$\begin{array}{cc}\hfill & 2x+4y+3z=2\text{,}\hfill \\ \hfill & 3x+y+2z=1\text{,}\hfill \\ \hfill & 4x-2y+z=-1\text{.}\hfill \end{array}$

4.6.4

$\begin{array}{cc}\hfill & x-y+2z=0\text{,}\hfill \\ \hfill & 2x+z=0\text{,}\hfill \\ \hfill & x+3y-z=0\text{.}\hfill \end{array}$

4.6.5

$\begin{array}{cc}\hfill & \sqrt{6}x+2\sqrt{3}y+3\sqrt{2}z=0\text{,}\hfill \\ \hfill & \sqrt{2}x+2y+\sqrt{6}z=0\text{,}\hfill \\ \hfill & (1/\sqrt{2})x+y+\sqrt{1.5}z=0\text{.}\hfill \end{array}$

4.6.6

$\begin{array}{cc}\hfill & \sqrt{6}x+2\sqrt{3}y+3\sqrt{2}z=\sqrt{3}\text{,}\hfill \\ \hfill & \sqrt{2}x+2y+\sqrt{6}z=2\text{,}\hfill \\ \hfill & (1/\sqrt{2})x+y+\sqrt{1.5}z=1\text{.}\hfill \end{array}$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128010006000043

Determinants and Eigenvalues

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fifth Edition), 2016

Techniques for Finding the Determinant of an n × n Matrix A

■

2×2 case: $\left|\mathbf{A}\right|=a_{11}{a}_{22}-a_{12}{a}_{21}$ (Sections 2.4 and 3.1).

■

3×3 case: Basketweaving (Section 3.1).

•

Row reduction: Row reduce A to an upper triangular form matrix B, keeping track of the effect of each row operation on the determinant using a variable P. Then $|\mathbf{A}|=(\frac{1}{P})|\mathbf{B}|$ , using the final value of P. Advantages: easily computerized; relatively efficient (Section 3.2).

■

Cofactor expansion: Multiply each element along any row or column of A by its cofactor and sum the results. Advantage: useful for matrices with many zero entries. Disadvantage: not as fast as row reduction (Sections 3.1 and 3.3).

Also remember that $\left|\mathbf{A}\right|=0$ if A is row equivalent to a matrix with a row or column of zeroes, or with two identical rows, or with two identical columns.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128008539000037

Gaussian Elimination and the LU Decomposition

William Ford , in Numerical Linear Algebra with Applications, 2015

In Chapter 2, we presented the process of solving a nonsingular linear system Ax = b using Gaussian elimination. We formed the augmented matrix A |b and applied the elementary row operations

1.

Multiplying a row by a scalar.

2.

Subtracting a multiple of one row from another

3.

Exchanging two rows

to reduce A to upper-triangular form. Following this step, back substitution computed the solution. In many applications where linear systems appear, one needs to solve Ax = b for many different vectors b. For instance, suppose a truss must be analyzed under several different loads. The matrix remains the same, but the right-hand side changes with each new load. Most of the work in Gaussian elimination is applying row operations to arrive at the upper-triangular matrix. If we need to solve several different systems with the same A, then we would like to avoid repeating the steps of Gaussian elimination on A for every different b. This can be accomplished by the LU decomposition, which in effect records the steps of Gaussian elimination.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123944351000119

Integer Discrete Cosine/Sine Transforms

Vladimir Britanak , ... K.R. Rao , in Discrete Cosine and Sine Transforms, 2007

5.2.7 QR, LU, LDU and PLUS factorizations

We mentioned that in linear algebra and matrix computations, a real nonsingular matrix is reduced by elementary rotation matrices and elementary transformations into various canonical forms in order to simplify subsequent computational steps of a solved problem.

Such procedures lead to various useful factorizations of the matrix into the products of structurally simpler matrices.

There exist two basic methods how to reduce a real nonsingular matrix of order N into equivalent upper triangular form. The first method is based on premultiplications of the matrix by elementary Givens–Jacobi rotation matrices. This procedure leads to the well-known QR factorization, where Q is an orthogonal matrix and R is an upper triangular matrix. The QR factorization is also discussed in the Appendix A.3 (see equations (A.27)–(A.34)). The following theorem and corollaries state the QR factorization [1].

Theorem 5.1: ([1], Chapter 1, p. 37)

Arbitrary real nonsingular matrix

$A=\left(\begin{array}{cccc}{a}_{11}^{(0)}& a_{12}^{(0)}& \cdots & a_{1n}^{(0)}\\ a_{21}^{(0)}& a_{22}^{(0)}& \cdots & a_{2n}^{(0)}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}^{(0)}& a_{n2}^{(0)}& \cdots & a_{nn}^{(0)}\end{array}\right)$

can be reduced through successive premultiplications by elementary Givens–Jacobi rotation matrices G_ij to an upper triangular matrix, whose all diagonal elements are positive besides the last one, i.e.,

$A^{(n-1)}=G_{n-1,n\cdots }{G}_{13}{G}_{12}A=\left(\begin{array}{cccc}{a}_{11}^{(1)}& a_{12}^{(1)}& \cdots & a_{1n}^{(1)}\\ 0& a_{22}^{(2)}& \cdots & a_{2n}^{(2)}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}^{(n-1)}\end{array}\right).$

•

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123736246500072

Matrices

Richard Bronson , ... John T. Saccoman , in Linear Algebra (Third Edition), 2014

1.7 LU Decomposition

Matrix inversion of elementary matrices is at the core of still another popular method, known as LU decomposition, for solving simultaneous equations in the matrix form Ax  = b. The method rests on factoring a nonsingular coefficient matrix A into the product of a lower triangular matrix L with an upper triangular matrix U. Generally, there are many such factorizations. If L is required to have all diagonal elements equal to 1, then the decomposition, when it exists, is unique and we may write

(1.33) $\mathbf{A}=\mathbf{LU}$

with

$\mathbf{L}=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill l_{21}\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill l_{31}\hfill & \hfill l_{32}\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill l_{n1}\hfill & \hfill l_{n2}\hfill & \hfill l_{n3}\hfill & \hfill \cdots \hfill & \hfill 1\hfill \end{array}\right]$

$\mathbf{U}=\left[\begin{array}{ccccc}\hfill u_{11}\hfill & \hfill u_{12}\hfill & \hfill u_{13}\hfill & \hfill \cdots \hfill & \hfill u_{1n}\hfill \\ \hfill 0\hfill & \hfill u_{22}\hfill & \hfill u_{23}\hfill & \hfill \cdots \hfill & \hfill u_{2n}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill u_{23}\hfill & \hfill \cdots \hfill & \hfill u_{3n}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill u_{\mathit{nn}}\hfill \end{array}\right]$

To decompose A into form (1.33), we first transform A to upper triangular form using just the third elementary row operation R ₃. This is similar to transforming a matrix to row-reduced form, except we no longer use the first two elementary row operations. We do not interchange rows, and we do not multiply rows by nonzero constants. Consequently, we no longer require that the first nonzero element of each nonzero row be 1, and if any of the pivots are 0—which would indicate a row interchange in the transformation to row-reduced form—then the decomposition scheme we seek cannot be done.

Example 1 Use the third elementary row operation to transform the matrix

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]$

into upper triangular form.

Solution:

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]\to \left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]$	by adding to the second row − 2 times the first row
$\to \left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill -4& \hfill 11\end{array}\right]$	by adding to the third row 3 times the first row
$\to \left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right]$	by adding to the third row 1 times the second row

If a square matrix A can be reduced to upper triangular form U by a sequence of elementary row operations of the third type, then there exists a sequence of elementary matrices E ₂₁, E ₃₁, E ₄₁, …   , E _{n,n−   1} such that

(1.34) $\left({\mathbf{E}}_n{}_{,n–1}\dots {\mathbf{E}}_{41}{\mathbf{E}}_{31}{\mathbf{E}}_{21}\right)\mathbf{A}=\mathbf{U}$

where E ₂₁ denotes the elementary matrix that places a 0 in the 2-1 position, E ₃₁ denotes the elementary matrix that places a 0 in the 3-1 position, E ₄₁ denotes the elementary matrix that places a 0 in the 4-1 position, and so on. Since elementary matrices have inverses, we can write Equation (1.29) as

(1.35) $\mathbf{A}=\left({\mathbf{E}}_{21}^{-1}{\mathbf{E}}_{31}^{-1}{\mathbf{E}}_{41}^{-1}\dots {\mathbf{E}}_{n,n-1}^{-1}\right)\mathbf{U}$

Each elementary matrix in Equation (1.34) is lower triangular. It follows from Theorem 4 of Section 1.5 that each of the inverses in Equation (1.35) are lower triangular and then from Theorem 2 of Section 1.3 that the product of these lower triangular inverses is itself lower triangular. If we set

$\mathbf{L}=\left({\mathbf{E}}_{21}^{-1}{\mathbf{E}}_{31}^{-1}{\mathbf{E}}_{41}^{-1}\dots {\mathbf{E}}_{n,n-1}^{-1}\right)$

then L is lower triangular and Equation (1.35) may be rewritten as A  = LU, which is the decomposition we seek.

A square matrix A has an LU decomposition if A can be transformed to upper triangular form using only the third elementary row operation.

Example 2 Construct an LU decomposition for the matrix given in Example 1.

Solution: The elementary matrices associated with the elementary row operations described in Example 1 are

${\mathbf{E}}_{21}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill -2& \hfill 1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right],{\mathbf{E}}_{31}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill -3& \hfill 0& \hfill 1\end{array}\right],\text{and}{\mathbf{E}}_{32}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill -1& \hfill 1\end{array}\right]$

with inverses given respectively by

${\mathbf{E}}_{21}^{-1}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right],{\mathbf{E}}_{31}^{-1}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill -3& \hfill 0& \hfill 1\end{array}\right],\text{and}{\mathbf{E}}_{32}^{-1}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill -1& \hfill 1\end{array}\right].$

Then,

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill -3& \hfill 0& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill -1& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right]$

or, upon multiplying together the inverses of the elementary matrices,

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill -3& \hfill -1& \hfill 1\end{array}\right]\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right].$

Example 2 suggests an important simplification of the decomposition process. Note that the elements in L located below the main diagonal are the negatives of the scalars used in the elementary row operations in Example 1 to reduce A to upper triangular form! This is no coincidence.

▸Observation 1

If, in transforming a square matrix A to upper triangular form, a zero is placed in the i-j position by adding to row i a scalar k times row j, then the i-j element of L in the LU decomposition of A is − k.◂

We summarize the decomposition process as follows: Use only the third elementary row operation to transform a square matrix A to upper triangular form. If this is not possible, because of a zero pivot, then stop. Otherwise, the LU decomposition is found by defining the resulting upper triangular matrix as U and constructing the lower triangular matrix L according to Observation 1.

Example 3 Construct an LU decomposition for the matrix

$\mathbf{A}=\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 6& \hfill 2& \hfill 4& \hfill 8\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]$

Solution: Transforming A to upper triangular form, we get

$\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 6& \hfill 2& \hfill 4& \hfill 8\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]\to \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]$	by adding to the second row −   3 times the first row
$\to \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill -\frac{3}{2}& \hfill -1& \hfill \frac{5}{2}\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]$	by adding to the third row −   1/2 times the first row
$\to \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]$	by adding to the third row −   3/2 times the second row
$\to \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 0& \hfill -5& \hfill -5\end{array}\right]$	by adding to the fourth row 1 times the second row
$\to \left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 0& \hfill 0& \hfill 5\end{array}\right]$	by adding to the fourth row 5/2 times the third row

We now have an upper triangular matrix U. To get the lower triangular matrix L in the decomposition, we note that we used the scalar −   3 to place a 0 in the 2-1 position, so its negative −(−   3)   =   3 goes into the 2-1 position of L. We used the scalar −   1/2 to place a 0 in the 3-1 position in the second step of the preceding triangularization process, so its negative, 1/2, becomes the 3-1 element in L; we used the scalar 5/2 to place a 0 in the 4-3 position during the last step of the triangularization process, so its negative, −   5/2, becomes the 4-3 element in L. Continuing in this manner, we generate the decomposition

$\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 6& \hfill 2& \hfill 4& \hfill 8\\ \hfill 1& \hfill -1& \hfill 0& \hfill 4\\ \hfill 0& \hfill 1& \hfill -3& \hfill -4\end{array}\right]=\left[\begin{array}{rrrr}\hfill 1& \hfill 0& \hfill 0& \hfill 0\\ \hfill 3& \hfill 1& \hfill 0& \hfill 0\\ \hfill \frac{1}{2}& \hfill \frac{3}{2}& \hfill 1& \hfill 0\\ \hfill 0& \hfill -1& \hfill -\frac{5}{2}& \hfill 1\end{array}\right]\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill 2& \hfill 3\\ \hfill 0& \hfill -1& \hfill -2& \hfill -1\\ \hfill 0& \hfill 0& \hfill 2& \hfill 4\\ \hfill 0& \hfill 0& \hfill 0& \hfill 5\end{array}\right]$

LU decompositions, when they exist, are used to solve systems of simultaneous linear equations. If a square matrix A can be factored into A  = LU, then the system of equations Ax  = b can be written as L(Ux)  = b. To find x, we first solve the system

(1.36) $\mathbf{Ly}=\mathbf{b}$

for y, and then once y is determined, we solve the system

(1.37) $\mathbf{Ux}=\mathbf{y}$

for x. Both systems (1.36) and (1.37) are easy to solve, the first by forward substitution and the second by backward substitution.

If A  = LU for a square matrix A, then the equation Ax  = b is solved by first solving the equation Ly  = b for y and then solving the equation Ux  = y for x.

Example 4 Solve the system of equations:

$\begin{array}{c}\hfill 2x–y+3z=9\hfill \\ \hfill 4x+2y+z=9\hfill \\ \hfill –6x–y+2z=12\hfill \end{array}$

Solution: This system has the matrix form

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 4& \hfill 2& \hfill 1\\ \hfill -6& \hfill -1& \hfill 2\end{array}\right]\left[\begin{array}{l}x\\ y\\ z\end{array}\right]=\left[\begin{array}{r}\hfill 9\\ \hfill 9\\ 12\end{array}\right]$

The LU decomposition for the coefficient matrix A is given in Example 2. If we define the components of y by α, β, and γ, respectively, the matrix system Ly  = b is

$\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 2& \hfill 1& \hfill 0\\ \hfill -3& \hfill -1& \hfill 1\end{array}\right]\left[\begin{array}{l}\alpha \\ \beta \\ \gamma \end{array}\right]=\left[\begin{array}{r}9\\ 9\\ 12\end{array}\right]$

which is equivalent to the system of equations

$\begin{array}{c}\hfill \alpha =9\hfill \\ \hfill 2\alpha +\beta =9\hfill \\ \hfill -3\alpha -\beta +\gamma =12\hfill \end{array}$

Solving this system from top to bottom, we get α   =   9, β  =   −   9, and γ   =   30. Consequently, the matrix system Ux  = y is

$\left[\begin{array}{rrr}\hfill 2& \hfill -1& \hfill 3\\ \hfill 0& \hfill 4& \hfill -5\\ \hfill 0& \hfill 0& \hfill 6\end{array}\right]\left[\begin{array}{l}x\\ y\\ z\end{array}\right]=\left[\begin{array}{r}9\\ -9\\ 30\end{array}\right]$

which is equivalent to the system of equations

$\begin{array}{c}\hfill 2x–y+3z=9\hfill \\ \hfill 4y–5z=–9\hfill \\ \hfill 6z=30\hfill \end{array}$

Solving this system from bottom to top, we obtain the final solution x  =   −   1, y  =   4, and z  =   5.

Example 5 Solve the system

$\begin{array}{c}\hfill 2a+b+2c+3d=5\hfill \\ \hfill 6a+2b+4c+8d=8\hfill \\ \hfill a–b+4d=–4\hfill \\ \hfill b–3c–4d=–3\hfill \end{array}$

Solution: The matrix representation for this system has as its coefficient matrix the matrix A of Example 3. Define

$\mathbf{y}={\left[\alpha ,\beta ,\gamma ,\delta \right]}^{\mathrm{T}}$

Then, using the decomposition determined in Example 3, we can write the matrix system Ly  = b as the system of equations

$\begin{array}{c}\hfill \alpha =5\hfill \\ \hfill 3\alpha +\beta =8\hfill \\ \hfill \frac{1}{2}\alpha +\frac{3}{2}\beta +\gamma =-4\hfill \\ \hfill -\beta -\frac{5}{2}\gamma +\delta =-3\hfill \end{array}$

which has as its solution α   =   5, β  =   −   7, γ   =   4, and δ  =   0. Thus, the matrix system Ux  = y is equivalent to the system of equations

$\begin{array}{c}\hfill 2a+b+2c+3d=5\hfill \\ \hfill –b–2c–d=–7\hfill \\ \hfill 2c+4d=4\hfill \\ \hfill 5d=0\hfill \end{array}$

Solving this set from bottom to top, we calculate the final solution as a  =   −   1, b  =   3, c  =   2, and d  =   0.

Problems 1.7

In Problems 1 through 14, A and b are given. Construct an LU decomposition for the matrix A and then use it to solve the system Ax  = b for x.

(1)

$\mathbf{A}=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 3\hfill & \hfill 4\hfill \end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 1\\ \hfill -6\end{array}\right].$

(2)

$\mathbf{A}=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 2\hfill \end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 11\\ \hfill -2\end{array}\right].$

(3)

$\mathbf{A}=\left[\begin{array}{cc}\hfill 8\hfill & \hfill 3\hfill \\ \hfill 5\hfill & \hfill 2\hfill \end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 625\\ \hfill 550\end{array}\right].$

(4)

$\mathbf{A}=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right],\mathbf{b}=\left[\begin{array}{c}\hfill 4\\ \hfill 1\\ \hfill -1\hfill \end{array}\right].$

(5)

$\mathbf{A}=\left[\begin{array}{rrr}\hfill -1& \hfill 2& \hfill 0\\ \hfill 1& \hfill -3& \hfill 1\\ \hfill 2& \hfill -2& \hfill 3\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill -1\\ \hfill -2\\ \hfill 3\end{array}\right].$

(6)

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 2& \hfill 1& \hfill 3\\ \hfill 4& \hfill 1& \hfill 0\\ \hfill -2& \hfill -1& \hfill -2\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 10\\ \hfill -40\\ \hfill 0\end{array}\right].$

(7)

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 3& \hfill 2& \hfill 1\\ \hfill 4& \hfill 0& \hfill 1\\ \hfill 3& \hfill 9& \hfill 2\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 50\\ \hfill 80\\ \hfill 20\end{array}\right].$

(8)

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 1& \hfill 2& \hfill -1\\ \hfill 2& \hfill 0& \hfill 1\\ \hfill -1& \hfill 1& \hfill 3\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 80\\ \hfill 159\\ \hfill -75\end{array}\right].$

(9)

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 1& \hfill 2& \hfill -1\\ \hfill 0& \hfill 2& \hfill 1\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 8\\ \hfill -1\\ \hfill 5\end{array}\right].$

(10)

$\mathbf{A}=\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill 0\\ \hfill 3& \hfill 2& \hfill 0\\ \hfill 1& \hfill 1& \hfill 2\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 2\\ \hfill 4\\ \hfill 2\end{array}\right].$

(11)

$\mathbf{A}=\left[\begin{array}{rrrr}\hfill 1& \hfill 0& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 0& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 0\\ \hfill 0& \hfill 1& \hfill 1& \hfill 1\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 4\\ \hfill -3\\ \hfill -2\\ \hfill -2\end{array}\right].$

(12)

$\mathbf{A}=\left[\begin{array}{rrrr}\hfill 2& \hfill 1& \hfill -1& \hfill 3\\ \hfill 1& \hfill 4& \hfill 2& \hfill 1\\ \hfill 0& \hfill 0& \hfill -1& \hfill 1\\ \hfill 0& \hfill 1& \hfill 1& \hfill 1\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 1000\\ \hfill 200\\ \hfill 100\\ \hfill 100\end{array}\right].$

(13)

$\mathbf{A}=\left[\begin{array}{rrrr}\hfill 1& \hfill 2& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 2& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 2\\ \hfill 0& \hfill 1& \hfill 1& \hfill 1\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill 30\\ \hfill 30\\ \hfill 10\\ \hfill 10\end{array}\right].$

(14)

$\mathbf{A}=\left[\begin{array}{rrrr}\hfill 2& \hfill 0& \hfill 2& \hfill 0\\ \hfill 2& \hfill 2& \hfill 0& \hfill 6\\ \hfill -4& \hfill 3& \hfill 1& \hfill 1\\ \hfill 1& \hfill 0& \hfill 3& \hfill 1\end{array}\right],\mathbf{b}=\left[\begin{array}{r}\hfill -2\\ \hfill 4\\ \hfill 9\\ \hfill 4\end{array}\right].$

(15)

(a)

Use LU decomposition to solve the system

$\begin{array}{c}\hfill –x+2y=–9\hfill \\ \hfill 2x+3y=4\hfill \end{array}$

(b)

Use the decomposition to solve the preceding system when the right sides of the equations are replaced by 1 and −   1, respectively.

(16)

(a)

Use LU decomposition to solve the system

$\begin{array}{c}\hfill x+3y–z=–1\hfill \\ \hfill 2x+5y+z=4\hfill \\ \hfill 2x+7y–4z=–6\hfill \end{array}$

(b)

Use the decomposition to solve the preceding system when the right side of each equation is replaced by 10, 10, and 10, respectively.

(17)

Solve the system Ax  = b for the following vectors b when A is given as in Problem 4:

(a)

$\left[\begin{array}{r}\hfill 5\\ \hfill 7\\ \hfill -4\end{array}\right],$

(b)

$\left[\begin{array}{r}\hfill 2\\ \hfill 2\\ \hfill 0\end{array}\right],$

(c)

$\left[\begin{array}{r}\hfill 40\\ \hfill 50\\ \hfill 20\end{array}\right],$

(d)

$\left[\begin{array}{r}\hfill 1\\ \hfill 1\\ \hfill 3\end{array}\right].$

(18)

Solve the system Ax  = b for the following vectors b when A is given as in Problem 13:

(a)

$\left[\begin{array}{r}\hfill -1\\ \hfill 1\\ \hfill 1\\ \hfill 1\end{array}\right],$

(b)

$\left[\begin{array}{r}\hfill 0\\ \hfill 0\\ \hfill 0\\ \hfill 0\end{array}\right],$

(c)

$\left[\begin{array}{r}\hfill 190\\ \hfill 130\\ \hfill 160\\ \hfill 60\end{array}\right],$

(d)

$\left[\begin{array}{r}\hfill 1\\ \hfill 1\\ \hfill 1\\ \hfill 1\end{array}\right].$

(19)

Show that LU decomposition cannot be used to solve the system

$\begin{array}{c}\hfill 2y+z=–1\hfill \\ \hfill x+y+3z=8\hfill \\ \hfill 2x–y–z=1\hfill \end{array}$

but that the decomposition can be used if the first two equations are interchanged.

(20)

Show that LU decomposition cannot be used to solve the system

$\begin{array}{c}\hfill x+2y+z=2\hfill \\ \hfill 2x+4y–z=7\hfill \\ \hfill x+y+2z=2\hfill \end{array}$

but that the decomposition can be used if the first and third equations are interchanged.

(21)

(a)

Show that the LU decomposition procedure given in this section cannot be applied to

$\mathbf{A}=\left[\begin{array}{cc}\hfill 0\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 9\hfill \end{array}\right]$

(b)

Verify that A  = LU, when

$\mathbf{L}=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\text{and}\mathbf{U}=\left[\begin{array}{cc}\hfill 0\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 7\hfill \end{array}\right]$

(c)

Verify that A  = LU, when

$\mathbf{L}=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 1\hfill \end{array}\right]\text{and}\mathbf{U}=\left[\begin{array}{cc}\hfill 0\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 3\hfill \end{array}\right]$

(d)

Why do you think the LU decomposition procedure fails for this A? What might explain the fact that A has more than one LU decomposition?

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123914200000019

Given Triangular Form of Matrix Find Solution

Source: https://www.sciencedirect.com/topics/mathematics/upper-triangular-form

Share :