Lower Triangular Inverse

Definition

Definition: Given a LowerTriangularMatrix $L \in \Snxn$ , its inverse is given by $L^{-1} \in \Snxn$ where $L^{-1} L = L L^{-1} = I$ .

Theorems, Lemmas, and Corollaries

Theorem: Let $L \in \Snxn$ be a LowerTriangularMatrix and nonsingular. Then its inverse, $L^{-1}$ , is also LowerTriangular.

Theorem: A LowerTriangularMatrix $L \in \Snxn$ is nonsingular iff its diagonal elements are nonzero.

Theorem: Partition nonsingular LowerTriangularMatrix $L \in \Snxn$ as
$L \rightarrow \FlaTwoByTwo{ L_{TL} }{ L_{TR} }{ L_{BL} }{ L_{BR} }$ ,
where $L_{TL} \in \S^{k \times k}$ . Then
$L^{-1}= \FlaTwoByTwo{ L_{TL}^{-1} }{ 0 }{ - L_{BR}^{-1} L_{BL} L_{TL}^{-1} }{ L_{BR}^{-1} }$ .
Proof

Corollary: The inverse of a nonsingular lower triangular matrix is itself lower triangular.

How is it used?

Generally speaking, when solving a triangular system $L x = b $ one should not form the inverse of $L$ , $L^{-1}$ . Instead, one should solve the linear system. The inverse of a triangular matrix is sometimes used as part of the inversion of a square nonsingular matrix.

Algorithms

$L \becomes L^{-1}$ denotes the operation that overwrites a nonsingular LowerTriangularMatrix with its inverse.

Partitioned Matrix Expression

The PME for this operation is given by

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR}^{-1} }$

Here $L_{TL}, \hat{L}_{TL} \in \S^{k \times k}$ .

Loop-invariants

The above PME allows for eight different loop-invariants to be identified:

Invariant 1

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { \hat{L}_{BL}}{ \hat{L}_{BR} }$

Invariant 2

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} }{ \hat{L}_{BR} }$

Invariant 3

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { - \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR} }$

Invariant 4

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR} }$

Invariant 5

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { \hat{L}_{BL} }{ \hat{L}_{BR}^{-1} }$

Invariant 6

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} }{ \hat{L}_{BR}^{-1} }$

Invariant 7

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { - \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR}^{-1} }$

Invariant 8

$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR}^{-1} }$

Algorithmic variants

Variant 1	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 1	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 2	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 2	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 3	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 3	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 4	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 4	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 5	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 5	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 6	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 6	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 7	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 7	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 8	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 8	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC

Related Operations

More Information

LinearAlgebraWiki: LowerTriangularInverse (last edited 2008-04-15 15:51:04 by MarthaGanser)

Invariant 1	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { \hat{L}_{BL}}{ \hat{L}_{BR} }$
Invariant 2	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} }{ \hat{L}_{BR} }$
Invariant 3	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { - \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR} }$
Invariant 4	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL}^{-1} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR} }$
Invariant 5	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { \hat{L}_{BL} }{ \hat{L}_{BR}^{-1} }$
Invariant 6	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} }{ \hat{L}_{BR}^{-1} }$
Invariant 7	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { - \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR}^{-1} }$
Invariant 8	$\FlaTwoByTwo{ L_{TL} }{ 0 } { L_{BL} }{ L_{BR} } = \FlaTwoByTwo{ \hat{L}_{TL} }{ 0 } { - \hat{L}_{BR}^{-1} \hat{L}_{BL} \hat{L}_{TL}^{-1}}{ \hat{L}_{BR}^{-1} }$