ABSTRACT

A method for solving systems of linear equations is presented based on direct decomposition of the coefficient matrix using the form $LAX=LB=B^{\prime }$ . Elements of the reducing lower triangular matrix L can be determined using either row wise or column wise operations and are demonstrated to be sums of permutation products of the Gauss pivot row multipliers. These sums of permutation products can be constructed using a tree structure that can be easily memorized or alternatively computed using matrix products. The method requires only storage of the L matrix which is half in size compared to storage of the elements in the LU decomposition. Equivalence of the proposed method with both the Gauss elimination and LU decomposition is also shown in this paper.

Keywords:

Systems of Linear Equations, Gauss Elimination, LU Decomposition, Linear Equations, Matrix Inverse, Determinant

1. Introduction

Systems of linear equations or equations linearized for iterative solutions arise in many science and engineering problems [1] . Practical applications of systems of linear equations are many, examples of such application include applications in digital signal processing, linear programming problems, numerical analysis of non-linear problems and least square curve fitting [2] . Systems of equations are also historically reported to have provided a motivation for the development of digital computer as less cumbersome way of solving the equations [3] .

Gaussian elimination is a systematic way of reducing systems of linear equations into a triangularised matrix through addition of the independent equations [4] . Carl Fredrich Gauss, a great 19^th Century mathematician proposed the elimination method as part of his proof for a particular theorem [5] . When zeros appear on the diagonal of the coefficient matrix at a particular row during the reduction process, row interchange is made with row from below. The Gauss elimination method requires 2n³/3 operations for n by n system of equations [6] [7] .

The LU decomposition was developed by Alan Turing as an alternative way carrying out Gaussian elimination through factorization of the coefficient matrix into a product of upper and lower triangular matrices, namely, A = LU [8] . The system is solved in two consecutive steps using the equations LY = B and UX = Y [9] . The Doolittle method is one alternative way of the LU factorization in which the diagonal elements of the lower triangular matrix L are all set equal to one [7] . The Doolittle method requires n² number of operations [10] . The Crout method was developed by the American mathematician Prescott Crout. In the Crout method, the upper triangular matrix U has its diagonal elements all set to one [11] . The Crout method likewise requires n² number of operations.

The Cholesky factorization works for symmetric positive definite matrices. The coefficient matrix in the system of equation AX = B is factorized into A = LL^T where L is the lower triangular matrix with its transpose L^T being an upper triangular matrix. The solution involves solving successively for LY = B and L^TX = Y [12] . The Cholesky factorization as such can be taken as a special case of LU decomposition in which the coefficient matrix is a symmetric, positive definite, a non-singular matrix. Gaussian elimination for symmetric positive definite matrices does not need pivoting and take half of the work and storage requirement of LU decomposition method [13] [14] . The Cholesky method requires 2n²/3 number of operations [10] .

The QR decomposition transforms the system of equation AX = B into triangular system RX = Q^Tb where A = QR. The matrix Q is orthogonal (QQ^T = I) and R is an upper triangular matrix [15] [16] .

2. Method Development

The method proposed in this paper is based on reducing the coefficient matrix A in the system of linear equations AX = B using a single lower triangular reducing matrix L. The original coefficient matrix A is transformed into an upper triangular matrix U that allows solution through back substitution as is usual with both LU decomposition as well as Gauss elimination methods. For the original system of n by n linear equations given as:

$\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+a_{13}{x}_3+\cdots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+a_{23}{x}_3+\cdots +a_{2n}{x}_n=b_2\\ ⋮\\ a_{n1}{x}_1+a_{n2}{x}_2+a_{n3}{x}_3+\cdots +a_{nn}{x}_n=b_n\end{array}$ (1)

The matrix representation of Equation (1) will be:

$AX=B$ (2)

where A is the coefficient matrix having the elements a_ij of the original equations and B is the right hand side column vector containing the elements $b_1,b_2,\cdots ,b_n$ .

The proposed method establishes a solution that transforms both the coefficient matrix A and the right hand side column vector B as follows:

$LAX=UX=LB=B^{\prime }$ (3)

In other words the coefficient matrix and the right hand side column vector B are transformed through the equations:

$LA=U$ and $LB=B^{\prime }$ (4)

The procedure, therefore, essentially centers on determining the lower triangular matrix L that reduces the coefficient matrix A to an upper triangular matrix U. Let this matrix L be given through its elements l_ij so that:

$L=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ l_{21}& 1& 0& 0& 0& 0\\ l_{31}& l_{32}& 1& 0& 0& 0\\ l_{41}& l_{42}& l_{43}& 1& 0& 0\\ ⋮& ⋮& ⋮& \ddots & 1& 0\\ l_{n1}& l_{n2}& l_{n3}& \cdots & \cdots & 1\end{array}\right]$ (5)

The operation LA = U will reduce the coefficient matrix A in to an upper triangular matrix U given by:

$U=\left[\begin{array}{cccccc}{u}_{11}& u_{12}& u_{13}& u_{14}& \cdots & u_{1n}\\ 0& u_{22}& u_{23}& u_{24}& \cdots & u_{2n}\\ 0& 0& u_{33}& u_{34}& \cdots & u_{3n}\\ 0& 0& 0& u_{44}& \cdots & u_{4n}\\ 0& 0& 0& 0& \ddots & ⋮\\ 0& 0& 0& 0& \cdots & u_{nn}\end{array}\right]$ (6)

However, this proposed method does not need storage of the U matrix as only the L matrix needs to be determined and used to reduce both the A matrix and the right hand side column vector B. This is easily seen through the matrix operation involving the reducing matrix L only, namely,

$LAX=LB=B^{\prime }$ (7)

In this method, the l_ij elements will be written in terms of the Gauss pivot row multipliers m_ij of the Gauss elimination, and, as will be shown shortly, the l_ij elements are the sum of the permutation products of the m_ij multipliers assembled into a tree like structure for easy memorization. The elements l_ij will not remain constant during the reduction process as is normally the case with Gauss elimination or LU decomposition, but change as the reduction of A to U matrix progresses column wise or row wise as new members of the Gauss pivot row multipliers are added to the element l_ij.

Unlike the Gauss method which is restricted to column wise operation, in this method it is also possible to proceed row wise. In fact the row wise procedure will be followed to derive the l_ij elements.

Starting with row 2 of the lower triangular L matrix,, the only unknown is l₂₁ and in terms of the Gauss elimination pivot row multipliers m_ij, the pivot operation to educe u₂₁ to zero is given as:

$m_{21}{a}_{11}+a_{21}=0$ so that $m_{21}=-a_{21}/a_{11}$ (8)

For row 3, l₃₁ is determined through the pivot element a₁₁ so that:

$m_{31}{a}_{11}+a_{31}=0$ so that $m_{31}=-a_{31}/a_{11}$ (9)

For row 3 again, the remaining element l₃₂ is determined through the pivot element ${a^{\prime }}_{22}$ which is modified from the original value a₂₂ because of the earlier reduction operation on row 2. Hence the reduction to u₃₂ = 0 is given by:

$m_{32}\left(m_{21}{a}_{12}+a_{22}\right)+\left(m_{31}{a}_{12}+a_{32}\right)=0$ (10)

Collating the pivot row multipliers m with respect to the coefficient matrix A elements, namely, a_ij, Equation (10) becomes:

$\left(m_{31}+m_{32}{m}_{21}\right)a_{12}+m_{32}{a}_{22}+a_{32}=0$ (11)

Likewise the l_ij elements for row 4 are determined as follows:

For ( $u_{41}=0$ ),

$m_{41}{a}_{11}+a_{41}=0$ (12)

For ( $u_{42}=0$ ),

$\left(m_{41}+m_{42}{m}_{21}\right)a_{12}+m_{42}{a}_{22}+a_{42}=0$ (13)

For ( $u_{43}=0$ ),

$\left(m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right)a_{13}+\left(m_{42}+m_{43}{m}_{32}\right)a_{23}+a_{43}=0$ (14)

For a 4 × 4 L matrix, summarizing the l_ij elements, expressed in terms of the Gauss pivot row multipliers m shown above, will give the L matrix shown in Equation (15).

$L=\left[\begin{array}{cccc}1& 0& 0& 0\\ m_{21}& 1& 0& 0\\ m_{31}+m_{32}{m}_{21}& m_{32}& 1& 0\\ m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}& m_{42}+m_{43}{m}_{32}& m_{43}& 1\end{array}\right]$ (15)

It is easy to show that the m terms in the L matrix in Equation (15) form permutation products where by the number of terms correspond to coefficients of the binomial series expansion. For any element l_ij of the L matrix, the number of m-product terms is given by:

$N_m\left(i,j\right)=2^{i-j-1}$ (16)

The power of binomial expansion $K\left(i,j\right)$ is given by;

$K\left(i,j\right)=i-j-1$ (17)

For example, for l₄₁,

$N_m\left(4,1\right)=2^{4-1-1}=2^2=4$

This corresponds to the binomial expansion of power $K\left(4,1\right)=2$ , i.e., $\left\{\text{1},\text{2},\text{1}\right\}$ .

The permutation products l₄₁ as shown in the L matrix are:

$l_{41}=\left\{\begin{array}{c}{m}_{41},\\ m_{42}{m}_{21}+m_{43}{m}_{31},\\ m_{43}{m}_{32}{m}_{21}\end{array}\right\}$ (18)

For l₅₁ similarly,

$N_m\left(5,1\right)=2^{5-1-1}=2^3=8$

This corresponds to the binomial expansion of power $K\left(5,1\right)=3$ , i.e., $\left\{1,3,3,1\right\}$ .

The permutation m-products for l₅₁ of the L matrix are, therefore,

$l_{51}=\left\{\begin{array}{c}{m}_{51},\\ m_{54}{m}_{41}+m_{53}{m}_{31}+m_{52}{m}_{21},\\ m_{54}{m}_{42}{m}_{21}+m_{53}{m}_{32}{m}_{21}+m_{54}{m}_{43}{m}_{31},\\ m_{54}{m}_{43}{m}_{32}{m}_{21}\end{array}\right\}$ (19)

2.1. Tree-Like Structure of the m-Permutation Products

It is easy to enumerate the m-permutation products of l_ij as these products can be arranged in a tree-like structure. Taking the example of elements of l₅₁ for example, the tree structure shown in Figure 1 is formed.

2.2. Formula for Calculation of the Sum of Permutation Products

For the element l_ij of the lower triangular matrix L, with the number of m products N_m corresponding to the binomial coefficients of power K(i,j), the binomial coefficients N_m(r) for $r=0,1,2,\cdots ,K$ is given by:

$N_m\left(r\right)=C_r^K=\frac{K!}{\left(K-r\right)!r!}$ (20)

For example for l₄₁ with $K=4-1-1=2$ and $K\left(r\right)=\left\{0,1,2\right\}$ ;

$N_m\left(0\right)=C_0^2=\frac{2!}{\left(2-0\right)!0!}=1$

$N_m\left(1\right)=C_1^2=\frac{2!}{\left(2-1\right)!1!}=2$

$N_m\left(2\right)=C_2^2=\frac{2!}{\left(2-2\right)!2!}=1$

Hence, $N_m=1+2+1=4$ .

Similarly for l₅₁ with $K\left(5,1\right)=\text{5}-\text{1}-\text{1}=\text{3}$ and $K\left(r\right)=\left\{0,1,2,3\right\}$ ;

$N_m\left(0\right)=C_0^3=\frac{3!}{\left(3-0\right)!0!}=1$

$N_m\left(1\right)=C_1^3=\frac{3!}{\left(3-1\right)!1!}=3$

$N_m\left(2\right)=C_2^3=\frac{3!}{\left(3-2\right)!2!}=3$

$N_m\left(3\right)=C_3^3=\frac{3!}{\left(3-3\right)!3!}=1$

Once the N_m(r) values are determined corresponding to the binomial coefficients the sum of permutation products are calculated as follows:

As an example for l₅₁ with $K=\left\{0,\text{1},\text{2},\text{3}\right\}$ and taking K = 2 which contain 3 terms, the sum of permutation products $M_{ij}\left(K=2\right)$ is given by:

$M_{ij}\left(K=2\right)={\displaystyle \sum }_{S=i-1}^{K+1}{\displaystyle \sum }_{P=S-1}^{j+1}{m}_{iS}{m}_{SP}{m}_{pj}$ (21)

$M_{51}\left(K=2\right)={\displaystyle \sum }_{S=4}^3{\displaystyle \sum }_{P=S-1}^2{m}_{5S}{m}_{SP}{m}_{p1}$ (22)

$M_{51}\left(K=2\right)=m_{54}{m}_{43}{m}_{31}+m_{54}{m}_{42}{m}_{21}+m_{53}{m}_{32}{m}_{21}$ (23)

In general for any element l_ij, the m_ij sum of products can be calculated using the formula:

$M_{ij}\left(K\right)={\displaystyle \sum }_{S=i-1}^{K+1}{\displaystyle \sum }_{P=S-1}^K{\displaystyle \sum }_{Q=p-1}^{K-1}\cdots {\displaystyle \sum }_{t=K+1}^{j+1}{m}_{iS}{m}_{SP}{m}_{pq}\cdots m_{tj}$ (24)

Finally, the element l_ij is computed by summing the M_ij sum of products as follows:

$l_{ij}={\displaystyle \sum }_{W=0}^{W=K}{M}_{ij}\left(W\right)$ (25)

2.3. Matrix Solution to the Computation the l_ij Elements of the Lower Triangular Matrix L

The computation of elements of the lower triangular matrix L can be easily carried out using matrix multiplication. For any element l_ij the matrix multiplication takes the following form:

$l_{ij}=\left[\begin{array}{ccccc}{m}_{ij}& m_{ij+1}& m_{ij+2}& \cdots & m_{ii-1}\end{array}\right]\ast \left[\begin{array}{c}1\\ l_{j+1j}\\ l_{j+2j}\\ l_{j+3j}\\ ⋮\\ l_{i-1j}\end{array}\right]$ (26)

Equation (26) shows the l_ij can be determined from already determined previous values of l_kj where $j+1<k<i$ and the Gauss pivot row multipliers $m_{ij},m_{ij+1},m_{ij+2},\cdots ,m_{ii-1}$ .

Equation 26 can be summarized in the general matrix product form as follows. Considering the lower triangular matrix L of Equation (5) again;

$L=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ l_{21}& 1& 0& 0& 0& 0\\ l_{31}& l_{32}& 1& 0& 0& 0\\ l_{41}& l_{42}& l_{43}& 1& 0& 0\\ ⋮& ⋮& ⋮& \ddots & 1& 0\\ l_{n1}& l_{n2}& l_{n3}& \cdots & \cdots & 1\end{array}\right]$ (5)

The negative of the corresponding Gauss pivot row multipliers m_rs that are already determined at this stage are given by the matrix form L_LU;

$L_{LU}=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ -m_{21}& 1& 0& 0& 0& 0\\ -m_{31}& -m_{32}& 1& 0& 0& 0\\ -m_{41}& -m_{42}& -m_{43}& 1& 0& 0\\ ⋮& ⋮& ⋮& \ddots & 1& 0\\ -m_{n1}& -m_{n2}& -m_{n3}& \cdots & \cdots & 1\end{array}\right]$ (27)

The matrix L_LU is simply the L matrix of the LU decomposition method. This can be verified as follows:

To avoid confusion, let traditional LU decomposition method have its L matrix relabelled L_LU to make it different from the L matrix of the proposed direct decomposition procedure.

From the relationship A = L_LUU as well as LA = U, it follows that:

$A=L^{-1}U=L_{LU}U$ (28)

It follows then that:

$L^{-1}=L_{LU}$ or

$L=L_{LU}^{-1}$ or

$L\ast L_{LU}^{-1}=I$ (29)

in which I is the identity matrix. Therefore the L matrix is simply the inverse of the L matrix L_LU of the LU decomposition method.

The L matrix elements as shown in Equation (15) can be can be reproduced from the matrix equation

$L_{LU}\ast L=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ -m_{21}& 1& 0& 0& 0& 0\\ -m_{31}& -m_{32}& 1& 0& 0& 0\\ -m_{41}& -m_{42}& -m_{43}& 1& 0& 0\\ ⋮& ⋮& ⋮& \ddots & 1& 0\\ -m_{n1}& -m_{n2}& -m_{n3}& \cdots & \cdots & 1\end{array}\right]\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ l_{21}& 1& 0& 0& 0& 0\\ l_{31}& l_{32}& 1& 0& 0& 0\\ l_{41}& l_{42}& l_{43}& 1& 0& 0\\ ⋮& ⋮& ⋮& \ddots & 1& 0\\ l_{n1}& l_{n2}& l_{n3}& \cdots & \cdots & 1\end{array}\right]=I$ (30)

This computation will be illustrated for the 4 by 4 matrix of L shown in Equation 5 and later for the example of the 4 by 4 system of linear equations solved in the section that follows. Starting with the element l₂₁ the matrix form of Equation (30) will take the form:

$l_{21}=\left[m_{21}\right]\ast \left[1\right]=1$ (31)

For element l₃₁:

$l_{31}=\left[\begin{array}{cc}{m}_{31}& m_{32}\end{array}\right]\ast \left[\begin{array}{c}1\\ l_{21}\end{array}\right]=\left[\begin{array}{cc}{m}_{31}& m_{32}\end{array}\right]\ast \left[\begin{array}{c}1\\ m_{21}\end{array}\right]=m_{31}+m_{32}{m}_{21}$ (32)

For element l_32:

$l_{32}=\left[m_{32}\right]\ast \left[1\right]=m_{32}$ (33)

For element l₄₁:

$l_{41}=\left[\begin{array}{ccc}{m}_{41}& m_{42}& m_{43}\end{array}\right]\ast \left[\begin{array}{c}1\\ l_{21}\\ l_{31}\end{array}\right]$ (34)

$l_{41}=\left[\begin{array}{ccc}{m}_{41}& m_{42}& m_{43}\end{array}\right]\ast \left[\begin{array}{c}1\\ m_{21}\\ m_{31}+m_{32}{m}_{21}\end{array}\right]=m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}$ (35)

For element l₄₂:

$l_{42}=\left[\begin{array}{cc}{m}_{42}& m_{43}\end{array}\right]\ast \left[\begin{array}{c}1\\ l_{32}\end{array}\right]=\left[\begin{array}{cc}{m}_{42}& m_{43}\end{array}\right]\ast \left[\begin{array}{c}1\\ m_{32}\end{array}\right]=m_{42}+m_{43}{m}_{32}$ (36)

For element l₄₃:

$l_{43}=\left[m_{43}\right]$ (37)

This completes the L matrix for the 4 by 4 matrix shown in Equation (15), i.e.,

$L=\left[\begin{array}{cccc}1& 0& 0& 0\\ m_{21}& 1& 0& 0\\ m_{31}+m_{32}{m}_{21}& m_{32}& 1& 0\\ m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}& m_{42}+m_{43}{m}_{32}& m_{43}& 1\end{array}\right]$ (15)

2.4. Number of Operations Required

The number of operations required N_p are related to the determination of the elements of the L matrix only. It is apparent that similar to the LU decomposition, the order of operations is of power 2, i.e., for n by n matrix the number of operations required grows proportional to n². This is clearly seen as the number of l_ij across the rows for an arithmetic series, $1,2,3,\cdots ,n-1$ which sums to:

$N_p=\left(\frac{1+n-1}{2}\right)\ast \left(n-1\right)=\frac{n\left(n-1\right)}{2}=O\left(n^2\right)$ (38)

For example for a 4 by 4 L matrix

$N_p=\frac{4\times \left(4-1\right)}{2}=6$

The l_ij elements of the L matrix shown in Equation (5) show the six elements to be determined. Compared to the LU decomposition, the proposed method requires only half of the operations required for the LU decomposition. The reason is, unlike the LU method the $LAX=LB=B^{\prime }$ method does not require storage of the U elements, i.e., only the L matrix is needed to solve the system of linear equations.

2.5. Procedure for Determining Elements of the L Matrix

The computation of the l_ij elements of the lower triangular matrix L can be carried out either row wise or column wise using more or less the same procedure as outlined in the following step by step procedure.

Step 1: Initially set all the Gaussian pivot row multipliers m_rs of the element l_ij to zero values. During computation of a particular value of m_rs the most recent values of the other pivot row multipliers will be used. In other words, the values of m_rs will be updated once their values change because of successive row wise or column wise computation.

Step 2: Starting with the first column and second row and proceeding either row wise or column wise, calculate the m_rs value for which r = i and s = j. For example for the element l₂₁, the m value to be calculated is that of m₂₁ and at l₅₃ it would be m₅₃ that will be calculated. The matrix equation for the computation of the m values is that of LA = U in which for the element l_ij the equation takes the form:

$l_{ip}{a}_{pj}=u_{ij}=0$ (39)

since u_ij is zero for the upper triangular matrix for i > j.

Step 3: Proceed likewise for all the elements m_rs taking into account that fact that all the other m values are updated once a new value is computed for them as per step 2.

Step 4: After the computation of all the m values of the Gauss pivot multipliers is completed, form the L matrix elements l_ij using the summation rules of the permutation products involving the m products as given by Equation (24) and Equation (25) or using the matrix product given in Equation (30).

Step 5: Once the L matrix is formed compute the solution X vector of the system of equations AX = B using the formula shown in Equation (3), namely,

$LAX=LB=B^{\prime }$ (3)

In other words, the product LA results in the upper triangular matrix U which will allow the computation of the solution vector elements of X using back substitution.

As in the Gauss method, it is possible to check if a zero appears on the diagonal of the U = LA matrix, i.e., to check if u_ii = 0 for a given row i during the computation of the l_ij elements. In other words, for a given row i, a check can be made for the value of u_ii using the formula:

$u_{ii}=l_{ip}{a}_{pi}$ (40)

If the condition u_ii = 0 becomes true, row interchange can be made with rows from below in the equation.

Figure 2 shows a flow chart of the steps outlined above in solving a system of linear equations using the LA = U method. The procedure stated above will be illustrated with an example given below which is a 4 × 4 system of linear equations. Two methods are given, Method 1 using column wise operations and Method 2 using row wise operations.

3. Application Examples

Example 1:

The 4 × 4 system of linear equation shown below will be used to illustrate the

proposed method of solving systems of linear equations using direct decomposition of the A matrix, i.e. using the matrix reduction $LAX=UX=LB=B^{\prime }$ . The system of equation is:

$\left[\begin{array}{cccc}6& -2& 2& 4\\ 12& -8& 6& 10\\ 3& -13& 9& 3\\ -6& 4& 1& -18\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}16\\ 26\\ -19\\ -34\end{array}\right]$

Forming the lower triangular matrix L in the equation LA = U and using the undetermined Gauss pivot row multipliers m_rs, the matrix equation LA = U becomes;

$\begin{array}{l}\left[\begin{array}{cccc}1& 0& 0& 0\\ m_{21}& 1& 0& 0\\ m_{31}+m_{32}{m}_{21}& m_{32}& 1& 0\\ m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}& m_{42}+m_{43}{m}_{32}& m_{43}& 1\end{array}\right]\\ \times \left[\begin{array}{cccc}6& -2& 2& 4\\ 12& -8& 6& 10\\ 3& -13& 9& 3\\ -6& 4& 1& -18\end{array}\right]=\left[\begin{array}{cccc}{u}_{11}& u_{12}& u_{13}& u_{14}\\ 0& u_{22}& u_{23}& u_{24}\\ 0& 0& u_{33}& u_{34}\\ 0& 0& 0& u_{44}\end{array}\right]\end{array}$

Method 1 (Column wise operation)

Column 1 operations:

Initially all the m values will be set to zero as outlined in the steps for solving the system of equations. Starting with column 1 and at row 2, the equation $l_{2p}{a}_{p1}=u_{21}=0$ gives;

$m_{21}\left(6\right)+1\left(12\right)=0;m_{21}=-\frac{12}{6}=-2$

Since row 2 operation is completed at this stage, check for the occurrence of a zero on the new pivot element, $u_{22}\ne 0$ ; $u_{22}=l_{2p}{a}_{p2}\ne 0$ ;

$u_{22}=m_{21}\left(-2\right)+1\left(-8\right)=-2\left(-2\right)-8=-4\ne 0$ o.k.

For the third row operation at column 1;

$l_{3p}{a}_{p1}=u_{31}=0$ ; the unknown to be determined is m₃₁

$\left(m_{31}+m_{32}{m}_{21}\right)\left(6\right)+m_{32}\left(12\right)+1\left(3\right)=u_{31}=0$

Since m₃₂ is as initially set zero and not yet determined, the above equation reduces to;

$\left(m_{31}+0\ast m_{21}\right)\left(6\right)+0\left(12\right)+1\left(3\right)=u_{31}=0$

$m_{31}=-\frac{3}{6}=-\frac{1}{2}$

For the fourth row at column 1;

$l_{4p}{a}_{p1}=u_{41}=0$ ; the unknown to be determined is m₄₁

$\left(m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right)\left(6\right)+m_{42}+\left(m_{43}{m}_{32}\right)\left(12\right)+m_{43}\left(3\right)+1\left(-6\right)=0$

Since all the m terms corresponding to columns 2 and 3 are as they were initially set zero (still undetermined) the above equation reduces to;

$m_{41}\left(6\right)+1\left(-6\right)=0;m_{41}=\frac{6}{6}=1$

Column 2 operations:

Starting with row 3;

$u_{32}=l_{3p}{a}_{p2}=0$ ;

$\left(m_{31}+m_{32}{m}_{21}\right)\left(-2\right)+m_{32}\left(-8\right)+1\left(-13\right)=0$

$\left(-\frac{1}{2}+m_{32}\left(-2\right)\right)\left(-2\right)+m_{32}\left(-8\right)+1\left(-13\right)=0$

$1+4m_{32}-8m_{32}-13=0;m_{32}=\frac{12}{-4}=-3$

Since row 3 operation is completed at this stage, check the new pivot element u₃₃, i.e.,

$u_{33}=l_{3p}{a}_{p3}\ne 0$ ;

$\left(m_{31}+m_{32}{m}_{21}\right)\left(2\right)+m_{32}\left(6\right)+1\left(9\right)=u_{33}\ne 0$

$\left(-\frac{1}{2}+\left(-3\right)\left(-2\right)\right)\left(2\right)+\left(-3\right)\left(6\right)+1\left(9\right)=u_{33}\ne 0$

$\left(-1+12\right)-18+9=11-18+9=2=u_{33}\ne 0$ (acceptable)

Since $u_{33}\ne 0$ , there is no need for row interchange.

For row 4 column 2 operations;

$u_{42}=l_{4p}{a}_{p2}=0$ ;

$\begin{array}{l}\left(m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right)\left(-2\right)+\left(m_{42}+m_{43}{m}_{32}\right)\left(-8\right)\\ +m_{43}\left(-13\right)+1\left(4\right)=0\end{array}$

Since m₄₃ = 0 (not yet determined), the above equation reduces to;

$\begin{array}{l}\left[1+m_{42}\left(-2\right)+\left(0\right)m_{31}+\left(0\right)m_{32}{m}_{21}\right]\left(-2\right)+\left(m_{42}+\left(0\right)m_{32}\right)\left(-8\right)\\ +\left(0\right)\left(-13\right)+1\left(4\right)=0\end{array}$

$-2-4\ast m_{42}+4=0$

$m_{42}=-\frac{2}{-4}=\frac{1}{2}$

Column 3 operations;

Proceeding to row 4 since the upper rows are already determined;

$u_{43}=l_{4p}{a}_{p3}=0$

$\left[m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right]\left(2\right)+\left[m_{42}+m_{43}{m}_{32}\right]\left(6\right)+m_{43}\left(9\right)+1\left(1\right)=0$

$\begin{array}{l}\left[1+\left(\frac{1}{2}\right)\left(-2\right)+m_{43}\left(-\frac{1}{2}\right)+m_{43}\left(-3\right)\left(-2\right)\right]\left(2\right)+\left[\frac{1}{2}+m_{43}\left(-3\right)\right]\left(6\right)\\ +m_{43}\left(9\right)+1\left(1\right)=0\end{array}$

$2\ast \left(-\frac{1}{2}+6\right)m_{43}+3-18\ast m_{43}+9m_{43}+1=0$

$11\ast m_{43}-18\ast m_{43}+9\ast m_{43}+4=0$

$2\ast m_{43}+4=0;m_{43}=-\frac{4}{2}=-2$

Since row 4 is completed, check for the occurrence of a zero on the new pivot element, i.e., u_44.

$u_{44}=l_{4p}{a}_{p4}\ne 0$ ;

$\begin{array}{l}\left[m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right]\left(4\right)+\left[m_{42}+m_{43}{m}_{32}\right]\left(10\right)\\ +m_{43}\left(3\right)+1\left(-18\right)\ne 0\end{array}$

$\begin{array}{l}\left[1+\left(\frac{1}{2}\right)\left(-2\right)+\left(-2\right)\left(-\frac{1}{2}\right)+\left(-2\right)\left(-3\right)\left(-2\right)\right]\left(4\right)+\left[\frac{1}{2}+\left(-2\right)\left(-3\right)\right]\left(10\right)\\ +\left(-2\right)\left(3\right)+1\left(-18\right)\ne 0\end{array}$

$\left[1-1+1-12\right]\left(4\right)+\left[\frac{1}{2}+6\right]\left(10\right)-6-18\ne 0$

$-44+65-6-18=-3\ne 0$ (acceptable)

Now all the m pivot row multipliers are determined and the elements of the lower triangular matrix L can be determined as follows:

Column 1 elements

$l_{21}=m_{21}=-2$

$l_{31}=m_{31}+m_{32}{m}_{21}=\left(-\frac{1}{2}\right)+\left(-3\right)\left(-2\right)=-\frac{1}{2}+6=\frac{11}{2}$

$\begin{array}{c}{l}_{41}=m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\\ =1+\left(\frac{1}{2}\right)\left(-2\right)+\left(-2\right)\left(-\frac{1}{2}\right)+\left(-2\right)\left(-3\right)\left(-2\right)\end{array}$

$l_{41}=1-1+1-12=-11$

Column 2 elements:

$l_{32}=m_{32}=-3$

$l_{42}=m_{42}+m_{43}{m}_{32}=\frac{1}{2}+\left(-2\right)\left(-3\right)=\frac{13}{2}$

Column 3 elements:

$l_{43}=m_{43}=-2$

Since all the l elements of the low triangular matrix are determined, the L matrix can now be written as follows:

$L=\left[\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ \frac{11}{2}& -3& 1& 0\\ -11& \frac{13}{2}& -2& 1\end{array}\right]$

Matrix Computation of the L Matrix for the Example 1

The L matrix can be computed using the matrix form given by Equation 30, i.e.,

$L_{LU}\ast L=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ -m_{21}& 1& 0& 0& 0& 0\\ -m_{31}& -m_{32}& 1& 0& 0& 0\\ -m_{41}& -m_{42}& -m_{43}& 1& 0& 0\\ ⋮& ⋮& ⋮& \ddots & 1& 0\\ -m_{n1}& -m_{n2}& -m_{n3}& \cdots & \cdots & 1\end{array}\right]\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ l_{21}& 1& 0& 0& 0& 0\\ l_{31}& l_{32}& 1& 0& 0& 0\\ l_{41}& l_{42}& l_{43}& 1& 0& 0\\ ⋮& ⋮& ⋮& \ddots & 1& 0\\ l_{n1}& l_{n2}& l_{n3}& \cdots & \cdots & 1\end{array}\right]=I$

For the above example, Equation (30) takes the form:

$L_{LU}\ast L=\left[\begin{array}{cccc}1& 0& 0& 0\\ -m_{21}& 1& 0& 0\\ -m_{31}& -m_{32}& 1& 0\\ -m_{41}& -m_{42}& -m_{43}& 1\end{array}\right]\left[\begin{array}{cccc}1& 0& 0& 0\\ l_{21}& 1& 0& 0\\ l_{31}& l_{32}& 1& 0\\ l_{41}& l_{42}& l_{43}& 1\end{array}\right]=I$

Substituting the computed m values

$L_{LU}\ast L=\left[\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ \frac{1}{2}& 3& 1& 0\\ -1& -\frac{1}{2}& 2& 1\end{array}\right]\left[\begin{array}{cccc}1& 0& 0& 0\\ l_{21}& 1& 0& 0\\ l_{31}& l_{32}& 1& 0\\ l_{41}& l_{42}& l_{43}& 1\end{array}\right]=I$

For element l₂₁

$2+l_{21}=0;l_{21}=-2$

For element l₃₁:

$\frac{1}{2}+3\ast l_{21}+l_{31}=0$

$l_{31}=-\frac{1}{2}-3\ast \left(-2\right)=\frac{11}{2}$

For element l_32:

$3+l_{32}=0$

$l_{32}=-3$

For element l₄₁:

$-1\left(1\right)+\left(-\frac{1}{2}\right)\ast l_{21}+2\ast l_{31}+l_{41}=0$

$l_{41}=1+\left(\frac{1}{2}\right)\ast \left(-2\right)-2\ast \left(\frac{11}{2}\right)=-11$

For element l₄₂:

$-1\ast \left(\frac{1}{2}\right)+2\ast l_{32}+l_{42}=0$

$l_{42}=\frac{1}{2}-2\ast \left(-3\right)=\frac{13}{2}$

For element l₄₃:

$2+l_{43}=0$

$l_{43}=-2$

This completes the L matrix, i.e.,

$L=\left[\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ \frac{11}{2}& -3& 1& 0\\ -11& \frac{13}{2}& -2& 1\end{array}\right]$

The reduced matrix LA becomes;

$LA=\left[\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ \frac{11}{2}& -3& 1& 0\\ -11& \frac{13}{2}& -2& 1\end{array}\right]\left[\begin{array}{cccc}6& -2& 2& 4\\ 12& -8& 6& 10\\ 3& -13& 9& 3\\ -6& 4& 1& -18\end{array}\right]=\left[\begin{array}{cccc}6& -2& 2& 4\\ 0& -4& 2& 2\\ 0& 0& 2& -5\\ 0& 0& 0& -3\end{array}\right]$

Similarly, the operation $LB=B^{\prime }$ becomes;

$B^{\prime }=LB=\left[\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ \frac{11}{2}& -3& 1& 0\\ -11& \frac{13}{2}& -2& 1\end{array}\right]\left[\begin{array}{c}16\\ 26\\ -19\\ -34\end{array}\right]=\left[\begin{array}{c}16\\ -6\\ -9\\ -3\end{array}\right]$

Finally the reduced equation $LAX=LB=B^{\prime }$ takes the form:

$\left[\begin{array}{cccc}6& -2& 2& 4\\ 0& -4& 2& 2\\ 0& 0& 2& -5\\ 0& 0& 0& -3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}16\\ -6\\ -9\\ -3\end{array}\right]$

The elements of the solution vector X can now be determined by back substitution. Starting from the fourth row, x₄ is determined;

$x_4=-\frac{3}{-3}=1$

From the equation of row 3, x₃ is determined;

$2\left(x_3\right)-5\left(1\right)=-9$

$x_3=-\frac{4}{2}=-2$

Similarly using row 2 equation for x₂;

$-4\left(x_2\right)+2\left(-2\right)+2\left(1\right)=-6$

$x_2=\frac{-6+4-2}{-4}=\frac{-4}{-4}=1$

Finally x₁ is determined from equation of row 1;

$6\left(x_1\right)-2\left(1\right)+2\left(-2\right)+4\left(1\right)=16$

$x_1=\frac{16+2+4-4}{6}=\frac{18}{6}=3$

Therefore the solution vector X is given by:

$X^{\text{T}}=\left\{\begin{array}{cccc}3& 1& -2& 1\end{array}\right\}$

This completes the solution using the proposed method. The alternative solution given below is only useful up to the computation of the Gaussian pivot row multiplier m following which the computation of the elements of the L and U matrix and the procedure for the determination of the solution vector X would be the same as was demonstrated above and need not be repeated.

Method 2 (Row wise operation)

Row 2 operations:

Initially all the m values will be set to zero as outlined in the steps for solving the system of equations. Starting with row 2 and at column 1, the equation $l_{2p}{a}_{p1}=u_{21}=0$ gives;

$m_{21}\left(6\right)+1\left(12\right)=0;m_{21}=-\frac{12}{6}=-2$

Since row 2 operation is completed at this stage, check for the occurrence of a zero on the new pivot element, $u_{22}\ne 0$ ;

$u_{22}=l_{2p}{a}_{p2}\ne 0$ ;

$u_{22}=m_{21}\left(-2\right)+1\left(-8\right)=-2\left(-2\right)-8=-4\ne 0$ (acceptable)

Row 3 operations

For the third row operation at column 1;

$l_{3p}{a}_{p1}=u_{31}=0$ ; the unknown to be determined is m₃₁

$\left(m_{31}+m_{32}{m}_{21}\right)\left(6\right)+m_{32}\left(12\right)+1\left(3\right)=u_{31}=0$

Since the column 2 multiplier m₃₂ is as initially set zero and not yet determined at this stage, the above equation reduces to;

$\left(m_{31}+0\ast m_{21}\right)\left(6\right)+0\left(12\right)+1\left(3\right)=u_{31}=0$

$m_{31}=-\frac{3}{6}=-\frac{1}{2}$

For row 3 column 2;

$u_{32}=l_{3p}{a}_{p2}=0$ ;

$\left(m_{31}+m_{32}{m}_{21}\right)\left(-2\right)+m_{32}\left(-8\right)+1\left(-13\right)=0$

$\left(-\frac{1}{2}+m_{32}\left(-2\right)\right)\left(-2\right)+m_{32}\left(-8\right)+1\left(-13\right)=0$

$1+4m_{32}-8m_{32}-13=0;m_{32}=\frac{12}{-4}=-3$

Since row 3 operation is completed at this stage, check the new pivot element u₃₃, i.e.,

$u_{33}=l_{3p}{a}_{p3}\ne 0$ ;

$\left(m_{31}+m_{32}{m}_{21}\right)\left(2\right)+m_{32}\left(6\right)+1\left(9\right)=u_{33}\ne 0$

$\left(-\frac{1}{2}+\left(-3\right)\left(-2\right)\right)\left(2\right)+\left(-3\right)\left(6\right)+1\left(9\right)=u_{33}\ne 0$

$\left(-1+12\right)-18+9=11-18+9=2=u_{33}\ne 0$

Since $u_{33}\ne 0$ , there is no need for row interchange.

Row 4 operations

For the fourth row at column 1;

$l_{4p}{a}_{p1}=u_{41}=0$ ; the unknown to be determined is m₄₁

$\begin{array}{l}\left(m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right)\left(6\right)+m_{42}+\left(m_{43}{m}_{32}\right)\left(12\right)\\ +m_{43}\left(3\right)+1\left(-6\right)=0\end{array}$

Since all the m terms corresponding to columns 2 and 3 belonging to row 4 are as they were initially set zero (still undetermined) the above equation reduces to;

$m_{41}\left(6\right)+1\left(-6\right)=0;m_{41}=\frac{6}{6}=1$

For row 4 column 2 operations;

$u_{42}=l_{4p}{a}_{p2}=0$ ;

$\begin{array}{l}\left(m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right)\left(-2\right)+\left(m_{42}+m_{43}{m}_{32}\right)\left(-8\right)\\ +m_{43}\left(-13\right)+1\left(4\right)=0\end{array}$

Since the row 4 column 3 multiplier, m₄₃ = 0 (is not yet determined), the above equation reduces to;

$\begin{array}{l}\left[1+m_{42}\left(-2\right)+\left(0\right)m_{31}+\left(0\right)m_{32}{m}_{21}\right]\left(-2\right)+\left(m_{42}+\left(0\right)m_{32}\right)\left(-8\right)\\ +\left(0\right)\left(-13\right)+1\left(4\right)=0\end{array}$

$-2-4\ast m_{42}+4=0$

$m_{42}=-\frac{2}{-4}=\frac{1}{2}$

For row 4 column 3 operations:

$u_{43}=l_{4p}{a}_{p3}=0$

$\left[m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right]\left(2\right)+\left[m_{42}+m_{43}{m}_{32}\right]\left(6\right)+m_{43}\left(9\right)+1\left(1\right)=0$

$\begin{array}{l}\left[1+\left(\frac{1}{2}\right)\left(-2\right)+m_{43}\left(-\frac{1}{2}\right)+m_{43}\left(-3\right)\left(-2\right)\right]\left(2\right)+\left[\frac{1}{2}+m_{43}\left(-3\right)\right]\left(6\right)\\ +m_{43}\left(9\right)+1\left(1\right)=0\end{array}$

$2\ast \left(-\frac{1}{2}+6\right)m_{43}+3-18\ast m_{43}+9m_{43}+1=0$

$11\ast m_{43}-18\ast m_{43}+9\ast m_{43}+4=0$

$2\ast m_{43}+4=0;m_{43}=-\frac{4}{2}=-2$

Since row 4 is completed, check for the occurrence of a zero on the new pivot element, i.e., u_44.

$u_{44}=l_{4p}{a}_{p4}\ne 0$ ;

$\begin{array}{l}\left[m_{41}+m_{42}{m}_{21}+m_{43}{m}_{31}+m_{43}{m}_{32}{m}_{21}\right]\left(4\right)+\left[m_{42}+m_{43}{m}_{32}\right]\left(10\right)\\ +m_{43}\left(3\right)+1\left(-18\right)\ne 0\end{array}$

$\begin{array}{l}\left[1+\left(\frac{1}{2}\right)\left(-2\right)+\left(-2\right)\left(-\frac{1}{2}\right)+\left(-2\right)\left(-3\right)\left(-2\right)\right]\left(4\right)+\left[\frac{1}{2}+\left(-2\right)\left(-3\right)\right]\left(10\right)\\ +\left(-2\right)\left(3\right)+1\left(-18\right)\ne 0\end{array}$

$\left[1-1+1-12\right]\left(4\right)+\left[\frac{1}{2}+6\right]\left(10\right)-6-18\ne 0$

$-44+65-6-18=-3\ne 0$ (acceptable)

Now all the m pivot row multipliers are determined and the determination of the L and U matrices as well as the computation of the solution vector X would proceed in exactly the same manner as demonstrated in method 1, column wise operations.

The example provided above shows in clear steps the solution step for solving system of linear equations using direct decomposition of the form $LAX=LB=B^{\prime }$ . Once the L matrix is formed, it can be used to solve any variants of the equation AX = B in which the right hand side column vector B is changed. This is demonstrated in the example given below.

Example 2: let the right hand side column vector be changed to the following while the coefficient matrix A remains the same. The new column vector B is given as:

$B^{\text{T}}=\left\{\begin{array}{cccc}4& 6& 26& 69\end{array}\right\}$

In this case, since the L matrix in the equation LA has already been worked out, the only additional operation needed would be the computation of $LB=B^{\prime }$ . Equation (3), namely,

$LAX=LB=B^{\prime }$

would be used to determine the new solution vector X. Starting with the computation of $LB=B^{\prime }$ ;

$LB=B^{\prime }=\left[\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ \frac{11}{2}& -3& 1& 0\\ -11& \frac{13}{2}& -2& 1\end{array}\right]\left[\begin{array}{c}4\\ 6\\ 26\\ 69\end{array}\right]=\left[\begin{array}{c}4\\ -2\\ 30\\ 12\end{array}\right]$

Finally, the solution vector X is computed from $LAX=LB=B^{\prime }$ :

$\left[\begin{array}{cccc}6& -2& 2& 4\\ 0& -4& 2& 2\\ 0& 0& 2& -5\\ 0& 0& 0& -3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}4\\ -2\\ 30\\ 12\end{array}\right]$

The elements of the solution vector X can now be determined by back substitution. Starting from the fourth row, x₄ is determined;

$x_4=\frac{12}{-3}=-4$

From the equation of row 3, x₃ is determined;

$2\left(x_3\right)-5\left(-4\right)=30$

$x_3=\frac{30-20}{2}=5$

Similarly using row 2 equation for x₂;

$-4\left(x_2\right)+2\left(5\right)+2\left(-4\right)=-2$

$x_2=\frac{-2+8-10}{-4}=\frac{-4}{-4}=1$

Finally x₁ is determined from equation of row 1;

$6\left(x_1\right)-2\left(1\right)+2\left(5\right)+4\left(-4\right)=4$

$x_1=\frac{4+16-10+2}{6}=\frac{12}{6}=2$

Therefore, the solution vector X is given by:

$X^{\text{T}}=\left\{\begin{array}{cccc}2& 1& 5& -4\end{array}\right\}$

4. Discussion

The proposed method, developed and demonstrated with examples so far, shows that solution to linear systems of equation can be obtained through direct decomposition of the A matrix using the operation $LAX=LB=B^{\prime }$ . The method provides a clear procedure for direct computation of the L matrix, the only matrix that is needed to transform the original equation AX = B in to a reduced form, i.e., LAX = BX unlike for example the LU method which requires that both the L and U matrix be stored to find the solution through $AX=LUX=B$ . The elements l_ij of the lower triangular matrix L are shown to be sums of permutation products of the Gauss pivot row multipliers m_rs. The relationship between l_ij and m_rs is clearly established through a formula and it is easy to visually construct this relationship using a tree diagram that will assist in easy memorisation of the relationship. In addition (and as an alternative procedure) the relationship so established between elements l_ij of the lower triangular matrix L and the Gauss pivot row multipliers m_rs enables construction of the L matrix directly from the Gauss elimination steps.

The characteristic of Gauss elimination method is that the reduction to an upper triangular matrix can only proceed column wise. It is not possible to proceed row wise in the Gauss method. On the other hand, the LU decomposition requires alternate transition between the L and U elements for determining the LU compact matrix. By contrast, the proposed LA = U reduction method can proceed either column wise or row wise essentially giving the same result. This flexibility is demonstrated in the example shown above where it is easily seen that the computation of the Gauss pivot row multipliers remains more or less the same for both the row wise and column wise operations.

The storage requirement during the reduction process is related to the generation of the L matrix. Unlike the LU method, storage is needed only for the L matrix since the solution directly proceeds from the reduction $LAX=LB=B^{\prime }$ in which there is no need to store the U matrix. The number of elements that need change is of the order O(n²) as shown in Equation 38 and is typically half the number of operations required for the LU decomposition because in the LU decomposition both the L and U elements need to be determined and stored.

5. Conclusions

A direct decomposition of the coefficient matrix forming part of a system of linear equations using a single lower triangular reducing matrix L has been demonstrated as shown in this paper. The method allows solution to the system of linear equations to proceed through storage of a single lower triangular matrix L only, through which both the coefficient matrix A and the right hand side column vector B are transformed. Elements of the reducing matrix L are shown to be sums of permutation products of the pivot row multipliers of the Gauss elimination technique. These sums of permutation products, for any element of the reducing matrix L, can be easily constructed using a tree diagram that is relatively easy to memorize besides using the formula developed for the purpose. These L matrix elements can also be alternatively computed using matrix products. In the process of determining the elements of the L matrix, either row wise or column wise procedure can be followed essentially giving the same result which provides added flexibility to the proposed method. Equivalence of this newly proposed method with both the Gauss elimination and LU decomposition techniques has been established. In the case of the equivalence with Gauss elimination technique, elements of the L matrix are specified as functions of the Gauss pivot row multipliers. This also implies that it is possible to construct the reducing L matrix of the proposed direct decomposition method using the Gauss pivot row multipliers. As has been demonstrated, the L matrix can be directed constructed from the Gauss pivot row multipliers using the matrix product L_LuL = I. For the LU decomposition, the L matrix of the proposed method is simply the inverse of the L matrix of the LU decomposition. In terms of storage of computed values, it can be seen that the proposed method of direct decomposition using the transformation $LAX=LB=B^{\prime }$ needs only storage of the L matrix elements which is half in size compared with storage of all the L and U elements in the LU decomposition method.

Apart from providing added flexibility and simplicity, the proposed method would be of good educational value providing an alternative procedure for solving systems of linear equations.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Tiruneh, A.T., Debessai, T.Y., Bwembya, G.C. and Nkambule, S.J. (2019) The LA = U Decomposition Method for Solving Systems of Linear Equations. Journal of Applied Mathematics and Physics, 7, 2031-2051. https://doi.org/10.4236/jamp.2019.79140

References