Content deleted Content added
m →Forward and back substitution: Vectors are supposed to be bold, not matrices |
|||
| (42 intermediate revisions by 34 users not shown) | |||
Line 1:
{{Short description|Special kind of square matrix}}
{{distinguish|text=a [[triangular array]], a related concept}}
{{for|the rings|triangular matrix ring}}{{Redirects here|Triangularization|the geometric process|Triangulation}}
In
Because matrix equations with triangular matrices are easier to solve, they are very important in [[numerical analysis]]. By the [[LU decomposition]] algorithm, an [[invertible matrix]] may be written as the [[matrix multiplication|product]] of a lower triangular matrix ''L'' and an upper triangular matrix ''U'' [[if and only if]] all its leading principal [[minor (linear algebra)|
▲In the [[mathematics|mathematical]] discipline of [[linear algebra]], a '''triangular matrix''' is a special kind of [[square matrix]]. A square matrix is called '''{{visible anchor|lower triangular}}''' if all the entries ''above'' the [[main diagonal]] are zero. Similarly, a square matrix is called '''{{visible anchor|upper triangular}}''' if all the entries ''below'' the [[main diagonal]] are zero.
▲Because matrix equations with triangular matrices are easier to solve, they are very important in [[numerical analysis]]. By the [[LU decomposition]] algorithm, an [[invertible matrix]] may be written as the product of a lower triangular matrix ''L'' and an upper triangular matrix ''U'' [[if and only if]] all its leading principal [[minor (linear algebra)|minors]] are non-zero.
== Description ==
Line 34 ⟶ 33:
===Examples===
:<math>\begin{bmatrix}
1 &
\end{bmatrix}</math>
is
:<math>\begin{bmatrix}
1 &
2 &
4 & 9 &
\end{bmatrix}</math>
and
:<math>\begin{bmatrix}
1 & 4 & 1 \\
0 & 6 & 9 \\
0 & 0 & 1
\end{bmatrix}</math>
is the upper triangular for the non symmetric matrix:
:<math>\begin{bmatrix}
1 & 4 & 1 \\
99 & 6 & 9 \\
40 & 88 & 1
\end{bmatrix}</math>
==Forward and back substitution==
Line 67 ⟶ 82:
\end{matrix}</math>
Observe that the first equation (<math>\ell_{1,1} x_1 = b_1</math>) only involves <math>x_1</math>, and thus one can solve for <math>x_1</math> directly. The second equation only involves <math>x_1</math> and <math>x_2</math>, and thus can be solved once one substitutes in the already solved value for <math>x_1</math>. Continuing in this way, the <math>k</math>-th equation only involves <math>x_1,\dots,x_k</math>, and one can solve for <math>x_k</math> using the previously solved values for <math>x_1,\dots,x_{k-1}</math>. The resulting formulas are:
:<math>\begin{align}
x_1 &= \frac{b_1}{\ell_{1,1}}, \\
Line 77 ⟶ 90:
\end{align}</math>
A matrix equation with an upper triangular matrix
===Applications===
Line 90 ⟶ 103:
The [[determinant]] and [[Permanent (mathematics)|permanent]] of a triangular matrix equal the product of the diagonal entries, as can be checked by direct computation.
In fact more is true: the [[eigenvalue]]s of a triangular matrix are exactly its diagonal entries. Moreover, each eigenvalue occurs exactly ''k'' times on the diagonal, where ''k'' is its [[algebraic multiplicity]], that is, its [[Multiplicity of a root of a polynomial|multiplicity as a root]] of the [[characteristic polynomial]] <math>p_A(x)=\det(xI-A)</math> of ''A''. In other words, the characteristic polynomial of a triangular ''n''×''n'' matrix ''A'' is exactly
: <math>p_A(x) = (x-a_{11})(x-a_{22})\cdots(x-a_{nn})</math>,
that is, the unique degree ''n'' polynomial whose roots are the diagonal entries of ''A'' (with multiplicities).
To see this, observe that <math>xI-A</math> is also triangular and hence its determinant <math>\
==Special forms==
=== Unitriangular matrix ===
If the entries on the [[main diagonal]] of a (
Other names used for these matrices are '''unit''' (
All finite unitriangular matrices are [[unipotent]].
=== Strictly triangular matrix ===
If all of the entries on the main diagonal of a (
All finite strictly triangular matrices are [[nilpotent matrix|nilpotent]] of index at most ''n'' as a consequence of the [[Cayley–Hamilton theorem|Cayley-Hamilton theorem]].
=== Atomic triangular matrix ===
{{Main|Frobenius matrix}}
An '''atomic''' (
=== Block triangular matrix ===
{{Main|Block matrix}}
A block triangular matrix is a [[block matrix]] (partitioned matrix) that is a triangular matrix.
====Upper block triangular====
A matrix <math>A</math> is '''upper block triangular''' if
:<math>A = \begin{bmatrix}
A_{11} & A_{12} & \cdots & A_{1k} \\
0 & A_{22} & \cdots & A_{2k} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & A_{kk}
\end{bmatrix}</math>,
where <math>A_{ij} \in \mathbb{F}^{n_i \times n_j}</math> for all <math>i, j = 1, \ldots, k</math>.<ref name="bernstein2009">{{Cite book |last=Bernstein |first=Dennis S. |title=Matrix mathematics: theory, facts, and formulas |publisher=Princeton University Press |year=2009 |isbn=978-0-691-14039-1 |edition=2 |___location=Princeton, NJ |pages=168 |language=en}}</ref>
====Lower block triangular====
A matrix <math>A</math> is '''lower block triangular''' if
:<math>A = \begin{bmatrix}
A_{11} & 0 & \cdots & 0 \\
A_{21} & A_{22} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
A_{k1} & A_{k2} & \cdots & A_{kk}
\end{bmatrix}</math>,
where <math>A_{ij} \in \mathbb{F}^{n_i \times n_j}</math> for all <math>i, j = 1, \ldots, k</math>.<ref name="bernstein2009" />
==Triangularisability{{Anchor|Triangularizability}}==
A matrix that is [[similar matrix|similar]] to a triangular matrix is referred to as '''triangularizable'''. Abstractly, this is equivalent to stabilizing a [[flag (linear algebra)|flag]]: upper triangular matrices are precisely those that preserve the [[standard flag]], which is given by the standard ordered basis <math>(e_1,\ldots,e_n)</math> and the resulting flag <math>0 < \left\langle e_1\right\rangle < \left\langle e_1,e_2\right\rangle < \cdots < \left\langle e_1,\ldots,e_n \right\rangle = K^n.</math> All flags are conjugate (as the [[general linear group]] acts transitively on bases), so any matrix that stabilises a flag is similar to one that
Any complex square matrix is triangularizable.<ref name="axler"/> In fact, a matrix ''A'' over a [[field (mathematics)|field]] containing all of the eigenvalues of ''A'' (for example, any matrix over an [[algebraically closed field]]) is similar to a triangular matrix. This can be proven by using induction on the fact that ''A'' has an eigenvector, by taking the quotient space by the eigenvector and inducting to show that ''A''
A more precise statement is given by the [[Jordan normal form]] theorem, which states that in this situation, ''A'' is similar to an upper triangular matrix of a very particular form. The simpler triangularization result is often sufficient however, and in any case used in proving the Jordan normal form theorem.<ref name="axler"/><ref name="herstein">{{
In the case of complex matrices, it is possible to say more about triangularization, namely, that any square matrix ''A'' has a [[Schur decomposition]]. This means that ''A'' is unitarily equivalent (i.e. similar, using a [[unitary matrix]] as change of basis) to an upper triangular matrix; this follows by taking an Hermitian basis for the flag.
Line 131 ⟶ 170:
The basic result is that (over an algebraically closed field), the [[commuting matrices]] <math>A,B</math> or more generally <math>A_1,\ldots,A_k</math> are simultaneously triangularizable. This can be proven by first showing that commuting matrices have a common eigenvector, and then inducting on dimension as before. This was proven by Frobenius, starting in 1878 for a commuting pair, as discussed at [[commuting matrices]]. As for a single matrix, over the complex numbers these can be triangularized by unitary matrices.
The fact that commuting matrices have a common eigenvector can be interpreted as a result of [[Hilbert's Nullstellensatz]]: commuting matrices form a commutative algebra <math>K[A_1,\ldots,A_k]</math> over <math>K[x_1,\ldots,x_k]</math> which can be interpreted as a variety in ''k''-dimensional affine space, and the existence of a (common) eigenvalue (and hence a common eigenvector) corresponds to this variety having a point (being non-empty), which is the content of the (weak) Nullstellensatz.{{Citation needed|reason=The existence of a common eigenvector is not clear, see https://mathoverflow.net/questions/43298/commuting-matrices-and-the-weak-nullstellensatz|date=March 2021}} In algebraic terms, these operators correspond to an [[algebra representation]] of the polynomial algebra in ''k'' variables.
This is generalized by [[Lie's theorem]], which shows that any representation of a [[solvable Lie algebra]] is simultaneously upper triangularizable, the case of commuting matrices being the [[abelian Lie algebra]] case, abelian being a fortiori solvable.
More generally and precisely, a set of matrices <math>A_1,\ldots,A_k</math> is simultaneously triangularisable if and only if the matrix <math>p(A_1,\ldots,A_k)[A_i,A_j]</math> is [[nilpotent]] for all polynomials ''p'' in ''k'' ''non''-commuting variables, where <math>[A_i,A_j]</math> is the [[commutator]]; for commuting <math>A_i</math> the commutator vanishes so this holds. This was proven by Drazin, Dungey, and Gruenberg in 1951;<ref>{{
== Algebras of triangular matrices ==
Line 143 ⟶ 182:
* The sum of two upper triangular matrices is upper triangular.
* The product of two upper triangular matrices is upper triangular.
* The [[inverse matrix|inverse]] of an upper triangular matrix,
* The product of an upper triangular matrix and a scalar is upper triangular.
Line 162 ⟶ 201:
===Borel subgroups and Borel subalgebras===
{{main|Borel subgroup|Borel subalgebra}}
The set of invertible triangular matrices of a given kind (
Over the real numbers, this group is disconnected, having <math>2^n</math> components accordingly as each diagonal entry is positive or negative. The identity component is invertible triangular matrices with positive entries on the diagonal, and the group of all invertible triangular matrices is a [[semidirect product]] of this group and the group of [[Diagonal matrix|diagonal matrices]] with <math>\pm 1</math> on the diagonal, corresponding to the components.
Line 171 ⟶ 209:
The upper triangular matrices are precisely those that stabilize the [[Flag (linear algebra)|standard flag]]. The invertible ones among them form a subgroup of the general linear group, whose conjugate subgroups are those defined as the stabilizer of some (other) complete flag. These subgroups are [[Borel subgroup]]s. The group of invertible lower triangular matrices is such a subgroup, since it is the stabilizer of the standard flag associated to the standard basis in reverse order.
The stabilizer of a partial flag obtained by forgetting some parts of the standard flag can be described as a set of block upper triangular matrices (but its elements are ''not'' all triangular matrices). The conjugates of such a group are the subgroups defined as the stabilizer of some partial flag. These subgroups are called
=== Examples ===
The group of
== See also ==
Line 186 ⟶ 224:
== References ==
{{reflist}}
{{Matrix classes}}
[[Category:Numerical linear algebra]]
[[Category:Matrices (mathematics)]]
| |||