Content deleted Content added
Undid revision 1012407242 by 49.206.120.106 (talk) unexplained removal |
|||
| (38 intermediate revisions by 31 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 93 ⟶ 106:
: <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>\det(xI-A)</math> is the product of its diagonal entries <math>(x-a_{11})(x-a_{22})\cdots(x-a_{nn})</math>.<ref name="axler">{{
==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 stabilizes the standard flag.
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'' stabilizes a flag, and is thus triangularizable with respect to a basis for that flag.
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 133 ⟶ 174:
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 141 ⟶ 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 160 ⟶ 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 169 ⟶ 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 ===
Line 184 ⟶ 224:
== References ==
{{reflist}}
{{Matrix classes}}
[[Category:Numerical linear algebra]]
[[Category:Matrices (mathematics)]]
| |||