1
$\begingroup$

Let $A$ be a nonsingular square matrix ($m \times m$). Show $A$ has an $LU$ factorization if and only if for each $k$ with $ 1 \leq k \leq m$, the upper left block $A(1:k,1:k)$ is nonsingular.

Below is my attempt. Just checking if I'm correct and/or if there's a simpler way to look at it.


proof ($\implies$)

$A$ is nonsingluar and $A = LU$. Let $0 \neq a = \det(A)$. Then

$$a = \det(L)\det(U) \implies \det(L),\det(U) \neq 0$$

Since $L$ and $U$ are both triangular matrices their determinants are the products of their diagonal entries. Therefore none of either's diagonal entries are zero. It follows that every upper left block of $L$ and $U$ is nonsingular. Since the entries of the upper left blocks of $A$ are calculated by

$$A_{ij} = L_i\cdot U_j \, , \quad 1 \leq i,j \leq k$$

(row and column notation) then an upper left block of $A$, denoted $A'$ has a corresponding upper left block of multiplication of $LU$, denoted $L'U'$. Since $L',U'$ are nonsingular

$$(A')^{-1} = (U')^{-1}(L')^{-1}$$

Therefore, if $A$ is nonsingular and has an $LU$ factorization, then all of the upper left blocks of $A$ are nonsingular.

$(\Longleftarrow)$

If $A'$ is an arbitrary nonsingular upper left block of $A$, then it is row equivalent to an upper triangular matrix $U'$ in row echelon form. That is $A'$ can be transformed via elementary row operations into $U'$. These elementary row operations have a corresponding transformation matrix called $(L')^{-1}$ and

$$ (L')^{-1} = E_{\frac{k(k-1)}{2}}\dots E_1$$

Elementary matrices are all invertible so $(L')^{-1}$ is invertible and

$$A' = L'U'$$

$\endgroup$
  • $\begingroup$ In $\Longleftarrow$ you assume what you have to prove. $\endgroup$ – Algebraic Pavel Jun 14 '18 at 0:17
  • $\begingroup$ The pivots of the elimination can be expressed in terms of the block determinants. $\endgroup$ – DVD Oct 6 '18 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.