Important: The linalg package has been deprecated. Use the superseding command LinearAlgebra[LUDecomposition], instead.

- For information on migrating linalg code to the new packages, see examples/LinearAlgebraMigration.

The routine LUdecomp computes both the traditional LU decomposition and a modified PLU1R decomposition of the matrix A.  It returns U.

For matrices of floating-point entries, a partial (row) pivoting method is used.  For symbolic computation, pivoting is done only when a leading entry is zero.  The pivot (permutation) matrix is returned as P.

The basic decomposition generates a square unit lower triangular L factor and an upper triangular U factor with the same dimensions as A so that A = P*L*U.

The decomposition further factors U into U1*R where U1 is square upper triangular and R is the unique reduced row-echelon form of the matrix A.  In this case A = P*L*U1*R.

The det parameter is defined to be the determinant of the U1 factor. This is non-zero for all matrices.  When A has full rank, this will coincide with the determinant of A.

The rank parameter will be the rank of A.  This will be of questionable value if A is composed of floating-point values and is ill-conditioned.

U1 is assumed to be non-singular.  The matrix R, i.e. the row-echelon factor of A, will only be correct if this is the case.  If A has parameters in its entries, and for some values of the parameters det(U1) = 0, then the row-echelon form must be recomputed for these values of the parameters.

Note that this paper names the U1 factor simply U.

The command with(linalg,LUdecomp) allows the use of the abbreviated form of this command.

$\mathrm{with}\left(\mathrm{linalg}\right)\:$

$A≔\mathrm{matrix}\left(\left[\left[1\,-2\,3\,1\right]\,\left[2\,k\,6\,6\right]\,\left[-1\,3\,k-3\,0\right]\right]\right)$

$A≔\left[\begin{array}{cccc}1& \mathrm{-2}& 3& 1\\ 2& k& 6& 6\\ \mathrm{-1}& 3& k-3& 0\end{array}\right]$

$x≔\mathrm{LUdecomp}\left(A\,L='l'\,U='u'\,\mathrm{U1}='\mathrm{u1}'\,R='r'\,P='p'\,\det ='d'\,\mathrm{rank}='\mathrm{ran}'\right)$

$x≔\left[\begin{array}{cccc}1& \mathrm{-2}& 3& 1\\ 0& k+4& 0& 4\\ 0& 0& k& \frac{k}{k+4}\end{array}\right]$

$\mathrm{rank}\left(x\right)$

$3$

$\mathrm{evalm}\left(x\right)$

$\left[\begin{array}{cccc}1& \mathrm{-2}& 3& 1\\ 0& k+4& 0& 4\\ 0& 0& k& \frac{k}{k+4}\end{array}\right]$

$\mathrm{evalm}\left(l\right)$

$\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ \mathrm{-1}& \frac{1}{k+4}& 1\end{array}\right]$

$\mathrm{map}\left(\mathrm{normal}\,\mathrm{evalm}\left(l\&*u\right)\right)$

$\left[\begin{array}{cccc}1& \mathrm{-2}& 3& 1\\ 2& k& 6& 6\\ \mathrm{-1}& 3& k-3& 0\end{array}\right]$

$\mathrm{evalm}\left(r\right)$

$\left[\begin{array}{cccc}1& 0.& 0.& \frac{9+k}{k+4}\\ 0& 1& 0.& \frac{4}{k+4}\\ 0& 0& 1& \frac{1}{k+4}\end{array}\right]$

$\mathrm{evalm}\left(\mathrm{u1}\right)$

$\left[\begin{array}{ccc}1& \mathrm{-2}& 3\\ 0& k+4& 0\\ 0& 0& k\end{array}\right]$

$\det \left(\mathrm{u1}\right)$

$\left(k+4\right)k$

$x≔\mathrm{LUdecomp}\left(\mathrm{subs}\left(k=0\,\mathrm{op}\left(A\right)\right)\,R='r'\,\det ='d'\,\mathrm{rank}='\mathrm{ran}'\right)$

$x≔\left[\begin{array}{cccc}1& \mathrm{-2}& 3& 1\\ 0& 4& 0& 4\\ 0& 0& 0& 0\end{array}\right]$

$\mathrm{evalm}\left(r\right)$

$\left[\begin{array}{cccc}1& 0.& 3& 3\\ 0& 1& 0& 1\\ 0& 0& 0& 0\end{array}\right]$

$x≔\mathrm{LUdecomp}\left(\mathrm{subs}\left(k=-4\,\mathrm{op}\left(A\right)\right)\,R='r'\,\det ='d'\,\mathrm{rank}='\mathrm{ran}'\right)$

$x≔\left[\begin{array}{cccc}1& \mathrm{-2}& 3& 1\\ 0& 1& \mathrm{-4}& 1\\ 0& 0& 0& 4\end{array}\right]$

$\mathrm{evalm}\left(r\right)$

$\left[\begin{array}{cccc}1& 0.& \mathrm{-5}& 0.\\ 0& 1& \mathrm{-4}& 0.\\ 0& 0& 0& 1\end{array}\right]$

$d$

$4$

$\mathrm{ran}$

$3$

$A≔\mathrm{matrix}\left(\mathrm{evalf}\left(\left[\left[1\,2\,3\right]\,\left[2\,4\,5\right]\,\left[3\,6\,7\right]\right]\right)\right)$

$A≔\left[\begin{array}{ccc}1.& 2.& 3.\\ 2.& 4.& 5.\\ 3.& 6.& 7.\end{array}\right]$

$U≔\mathrm{LUdecomp}\left(A\,P='p'\,L='l'\right)$

$U≔\left[\begin{array}{ccc}3.& 6.& 7.\\ 0.& 0.& 0.666666666666667\\ 0.& 0.& 0.\end{array}\right]$

$\mathrm{evalm}\left(p\right)$

$\left[\begin{array}{ccc}0.& 1.& 0.\\ 0.& 0.& 1.\\ 1.& 0.& 0.\end{array}\right]$

Corless, Robert M.; Jeffrey, David; and Nerenberg, M. A. H. "The Row Echelon Decomposition of a Matrix." University of Western Ontario Tech Report AM-91-01, Department of Applied Mathematics, 1991.