linear algebramatrices
Given the matrix A=$ \left( \begin{array}{ccc}
1 & 2 & 3 & 4 \\
5 & 6 & 7 & 8\\
1 & -1 & 2 & 3 \\
2 & 1 & 1 &2\end{array} \right) $, write it in the $L_{4 \times 4}U_{4 \times 4}$, where L is the lower triangular matrix and U is the upper triangular matrix.
To be honest, I don't even understand what the question is asking of me, however I do know what upper and lower triangular matrices are.
Thanks in advance for your help.
I don't know whether you are dealing with $2\times 2$ matrices or general $n \times $n$ matrices. The result is true in either case.
It may not be clear to you what these spaces are. Define addition of matrices by adding corresponding entries. So for example $$\begin{bmatrix} 1 & 2\\ 0 & 3 \end{bmatrix} + \begin{bmatrix} 5 & 3\\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 6 & 5\\ 0 & 4 \end{bmatrix} $$ If $c$ is a constant (a scalar, a number) then you multiply a matrix by $c$ by multiplying each entry by $c$. So for example $$3\begin{bmatrix} 1 & 2\\ 0 & 3 \end{bmatrix} = \begin{bmatrix} 3 & 6\\ 0 & 9 \end{bmatrix} $$
A vector space of matrices is a collection $V$ of matrices (of the same size) such that if $A$ and $B$ are matrices in the collection, then so is the sum $A+B$, and also if $c$ is any scalar, then $cA$ is in the collection.
So typically a vector space of matrices will have many matrices in it. The only vector space of matrices that consists of a single matrix is the space whose only element is the all $0$'s matrix.
In particular, the identity matrix by itself ($1$'s down the main diagonal, $0$'s elsewhere) is not a subspace of the collection of $2\times 2$ matrices, for if the identity matrix $I$ is in the subspace, then $cI$ has to be in the subspace for all numbers $c$. The collection of all matrices which are $0$ off diagonal, and have all diagonal terms equal is a subspace of the space of all matrices. Maybe that will take care of part of your objection.
Let $V$ be any vector space, and take a collection $U$ of some of the elements of $V$. Then $U$ is called a subspace of $V$ if $U$ by itself is a vector space, meaning that the sum of any two elements of $U$ is in $U$, and any constant times an element of $U$ is in $U$.
You quoted something to the effect that a certain $D$ is a subspace of the space of upper triangular matrices. That's not true. The collection of all matrices of the shape you described, with everything off diagonal equal to $0$, is a subspace. So $D$ is supposed to be not a single matrix, it is a largish collection of matrices.
Now let's look at your particular problem. Let $V$ be the collection of all upper triangular matrices. Is this a vector space? Take any two upper triangular matrices $A$ and $B$. Is $A+B$ upper triangular? Yes. If $c$ is a constant, and $A$ is upper triangular, is $cA$ upper triangular? Yes. So $V$ is a vector space.
Let $D$ be the collection of all diagonal matrices? Is this a vector space? Yes, the sum of two diagonal matrices is diagonal, a constant times a diagonal matrix is a diagonal matrix. $D$ is a subspace of the upper triangular matrices, because any diagonal matrix is in particular upper triangular, it is a special upper triangular matrix.
There is a nice trick for calculating the inverse of any invertible upper triangular matrix, one which avoids the computation of complicated determinants. Since it works for any such upper (or lower) triangular matrix $T$ of any size $n$, I'll explain it in that context.
The first thing one needs to remember is that the determinant of a triangular matrix is the product of its diagonal entries. This may easily be seen by induction on $n$. It is trivially true if $n = 1$; for $n = 2$, we have
$T= \begin{bmatrix} t_{11} & t_{12} \\ 0 & t_{22} \end{bmatrix}, \tag{1}$
so obviously
$\det(T) = t_{11} t_{22}. \tag{2}$
If we now formulate the inductive hypothesis that
$\det(T) = \prod_1^k t_{ii} \tag{3}$
for any upper triangular $T$ of size $k$,
$T = [t_{ij}], \; \; 1 \le i, j \le k, \tag{4}$
then for $T$ of size $k + 1$ we have that
$\det(T) = t_{11} \det(T_{11}), \tag{5}$
where $T_{11}$ is the $k \times k$ matrix formed by deleting the first row and comumn of $T$. (4) follows easily from the expansion of $\det(T)$ in terms of its first-column minors (see this wikipedia page), since $t_{i1} = 0$ for $i \ge 2$. From our inductive hypothesis,
$\det(T_{11}) = \prod_2^{k + 1} t_{ii}, \tag{6}$
whence from (5)
$\det(T) = t_{11} \det(T_{11}) = t_{11} \prod_2^{k + 1} t_{ii} = \prod_1^{k + 1} t_{ii}, \tag{7}$
proving our assertion.
It follows immediately from (7) that the characteristic polynomial $p_T(\lambda)$ of $T$ is
$p_T(\lambda) = \det(T - \lambda I) = \prod_1^n (t_{ii} - \lambda), \tag{8}$
and from (8) that the eigenvalues of $T$ are precisely its diagonal entries, i.e. the $t_{ii}$, $1 \le i \le n$; also follows from (7) the related fact that $T$ is nonsingular, that is, $\det(T) \ne 0$, precisely when its diagonal entries are all nonzero.
For non-singular $T$ we may compute $T^{-1}$ as follows: write
$T = \Lambda + T_u, \tag{9}$
where $\Lambda$ is the diagonal matrix formed from the diagonal of $T$; viz.,
$\Lambda = [\delta_{ij} t_{ij}]; \tag{10}$
then $\Lambda$ is nonsingular and $T_u = T - \Lambda$ is the strictly upper triangular matrix obtained by setting the diagonal of $T$ to zero, i.e. setting $t_{ii} = 0$ for $1 \le i \le n$. We may write
$T = \Lambda (I + \Lambda^{-1} T_u), \tag{11}$
whence
$T^{-1} = (I + \Lambda^{-1} T_u)^{-1} \Lambda^{-1}. \tag{12}$
The matrix $\Lambda^{-1} T_u$ occurring in (12) is itself in fact strictly upper triagnular as well as is $T_u$; indeed, for any diagonal $D$, $DT_u$ is strictly upper tirangular, an assertion which is easily validated by direct calculation. It follows that $\Lambda^{-1} T_u$ is in fact nilpotent; that is, $(\Lambda^{-1} T_u)^n = 0$. We may now use the well-known algebraic identity
$(1 + x)(\sum_0^m (-x)^j) = 1 - (-x)^{m + 1}, \tag{13}$
easily seen to hold in any unital ring, applied to the matrix $x =\Lambda^{-1} T_u$, yielding, with $m = n - 1$,
$(I + \Lambda^{-1}T_u)(\sum_0^m (-\Lambda^{-1}T_u)^j) = I - (-\Lambda^{-1}T_u)^{m + 1} = I - (-\Lambda^{-1}T_u)^n = I. \tag{13}$
(13) shows that the inverse of $I + \Lambda^{-1}T_u$ is given by
$(I + \Lambda^{-1} T_u)^{-1} = \sum_0^m (-\Lambda^{-1}T_u)^j. \tag{14}$
It follows from (14) that $(I + \Lambda T_u)^{-1}$ is upper triangular, since each of the matrices $(-\Lambda^{-1}T_u)^j$, $j \ge 1$, is strictly upper triangular, and $(-\Lambda^{-1}T_u)^0 = I$. It further follows then that $T^{-1} = (I + \Lambda T_u)^{-1}\Lambda^{-1}$ is also upper triangular, being the product of the upper triangular matrix $(I + \Lambda T_u)^{-1}$ and the diagonal matrix $\Lambda^{-1}$. We have thus shown that the inverse of any invertible upper triangular matrix, of any size $n$, is itself an upper triangular matrix.
The inverse of any invertible matrix is invertible, the inverse of the inverse being the original matrix.
We can apply these considerations to the calculation of $A^{-1}$, where
$A = \begin{bmatrix} a & b & c \\ 0 & d & e \\ 0 & 0 & f \end{bmatrix}; \tag{14}$
here we have
$\Lambda = \begin{bmatrix} a & 0 & 0 \\ 0 & d & 0 \\ 0 & 0 & f \end{bmatrix} \tag{15}$
and
$T_u = \begin{bmatrix} 0 & b & c \\ 0 & 0 & e \\ 0 & 0 & 0 \end{bmatrix}; \tag{16}$
then
$\Lambda^{-1} T_u = \begin{bmatrix} a^{-1} & 0 & 0 \\ 0 & d^{-1} & 0 \\ 0 & 0 & f^{-1} \end{bmatrix} \begin{bmatrix} 0 & b & c \\ 0 & 0 & e \\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & ba^{-1} & ca^{-1} \\ 0 & 0 & ed^{-1} \\ 0 & 0 & 0 \end{bmatrix}; \tag{17}$
$(\Lambda^{-1} T_u)^2 = \begin{bmatrix} 0 & ba^{-1} & ca^{-1} \\ 0 & 0 & ed^{-1} \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & ba^{-1} & ca^{-1} \\ 0 & 0 & ed^{-1} \\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & bea^{-1}d^{-1} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}; \tag{18}$
$(\Lambda^{-1} T_u)^3 = 0; \tag{19}$
$\sum_0^2 (-\Lambda^{-1} T_u)^j = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} - \begin{bmatrix} 0 & ba^{-1} & ca^{-1} \\ 0 & 0 & ed^{-1} \\ 0 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & bea^{-1}d^{-1} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$ $= \begin{bmatrix} 1 & -ba^{-1} & (be - cd)a^{-1}d^{-1} \\ 0 & 1 &- ed^{-1} \\ 0 & 0 & 1 \end{bmatrix}; \tag{20}$
finally,
$T^{-1} = (I + \Lambda^{-1} T_u)^{-1} \Lambda^{-1} = (\sum_0^2 (-\Lambda^{-1} T_u)^j) \Lambda^{-1}$ $= \begin{bmatrix} 1 & -ba^{-1} & (be - cd)a^{-1}d^{-1} \\ 0 & 1 &- ed^{-1} \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} a^{-1} & 0 & 0 \\ 0 & d^{-1} & 0 \\ 0 & 0 & f^{-1} \end{bmatrix}$ $= \begin{bmatrix} a^{-1} & -ba^{-1}d^{-1} & (be - cd)a^{-1}d^{-1}f^{-1} \\ 0 & d^{-1} &- ed^{-1}f^{-1} \\ 0 & 0 & f^{-1} \end{bmatrix}, \tag{21}$
this in agreement with Nimda's calculations. Indeed, we have
$\begin{bmatrix} a & b & c \\ 0 & d & e \\ 0 & 0 & f \end{bmatrix}\begin{bmatrix} a^{-1} & -ba^{-1}d^{-1} & (be - cd)a^{-1}d^{-1}f^{-1} \\ 0 & d^{-1} &- ed^{-1}f^{-1} \\ 0 & 0 & f^{-1} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \tag{22}$
as some simple algebra reveals.
Of course all this stuff applies to lower triangular matrices as well, and the demonstrations are similar and analogous, that is, essentially the same.
Hope this helps! Cheers,
and as always,
Fiat Lux!!!
Best Answer
As @Julien pointed out, every square matrix admits a $PLU$ decomposition, where $P$ is a permutation matrix. We have: $A = P \cdot L \cdot U$, such that:
$A=\begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\0 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\\1 & 1 & 0 & 0\\2 & 1 & 1 & 0\\5 & \dfrac{4}{3} & \dfrac{5}{3} & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 & 4\\0 & -3 & -1 & -1\\0 & 0 & -4 & -5\\0 & 0 & 0 & -\dfrac{7}{3} \end{bmatrix}$
You could try manually cranking this one to find its $LU$ factorization. We want:
$L \cdot U = \begin{bmatrix} 1 & 0 & 0 & 0\\l_{21} & 1 & 0 & 0\\l_{31} & l_{32} & 1 & 0\\l_{41} & l_{42} & l_{43} & 1 \end{bmatrix} \cdot \begin{bmatrix} 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{bmatrix} = \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}$
We start off by solving the first row, so we get:
$$u_{11} = 1, u_{12} = 2, u_{13} = 3, u_{14} = 4$$
The portion of the multiplication that determines the remaining entries in the first column of $A$ yields:
$$l_{21}u_{11} = 5 \rightarrow l_{21} = 5$$
$$l_{31}u_{11} = 1 \rightarrow l_{31} = 1$$
$$l_{11}u_{11} = 2 \rightarrow l_{41} = 2$$
At this point rewrite all the variables you solved for and then continue the process and see if you can solve the remaining variables. Of course it is easy to check the result if you can solve all of the equations.
So, we currently have:
$L \cdot U = \begin{bmatrix} 1 & 0 & 0 & 0\\5 & 1 & 0 & 0\\1 & l_{32} & 1 & 0\\2 & l_{42} & l_{43} & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 & 4\\0 & u_{22} &u_{23} & u_{24}\\0 & 0 & u_{33} & u_{34}\\0 & 0 & 0 & u_{44} \end{bmatrix} = \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}$
Try solving for $u_{22},u_{23}, u_{24}$, and then $l_{32}, l_{42}$ and continue this process.