Diagonally dominant matrix

In mathematics, a square matrix is said to be diagonally dominant if for every row of the matrix, the magnitude of the diagonal entry in a row is larger than or equal to the sum of the magnitudes of all the other (non-diagonal) entries in that row. More precisely, the matrix A is diagonally dominant if

|a_{ii}|\geq \sum _{j\neq i}|a_{ij}|\quad {\text{for all }}i,\,

where a_ij denotes the entry in the ith row and jth column.

Note that this definition uses a weak inequality, and is therefore sometimes called weak diagonal dominance. If a strict inequality (>) is used, this is called strict diagonal dominance. The unqualified term diagonal dominance can mean both strict and weak diagonal dominance, depending on the context.^[1]

Variations

The definition in the first paragraph sums entries across rows. It is therefore sometimes called row diagonal dominance. If one changes the definition to sum down columns, this is called column diagonal dominance.

Any strictly diagonally dominant matrix is trivially a weakly chained diagonally dominant matrix. Weakly chained diagonally dominant matrices are nonsingular and include the family of irreducibly diagonally dominant matrices. These are irreducible matrices that are weakly diagonally dominant, but strictly diagonally dominant in at least one row.

Examples

The matrix

A={\begin{bmatrix}3&-2&1\\1&-3&2\\-1&2&4\end{bmatrix}}

is diagonally dominant because

|a_{11}|\geq |a_{12}|+|a_{13}|

since

|+3|\geq |-2|+|+1|

|a_{22}|\geq |a_{21}|+|a_{23}|

since

|-3|\geq |+1|+|+2|

|a_{33}|\geq |a_{31}|+|a_{32}|

since

|+4|\geq |-1|+|+2|

The matrix

B={\begin{bmatrix}-2&2&1\\1&3&2\\1&-2&0\end{bmatrix}}

is not diagonally dominant because

|b_{11}|<|b_{12}|+|b_{13}|

since

|-2|<|+2|+|+1|

|b_{22}|\geq |b_{21}|+|b_{23}|

since

|+3|\geq |+1|+|+2|

|b_{33}|<|b_{31}|+|b_{32}|

since

|+0|<|+1|+|-2|

That is, the first and third rows fail to satisfy the diagonal dominance condition.

The matrix

C={\begin{bmatrix}-4&2&1\\1&6&2\\1&-2&5\end{bmatrix}}

is strictly diagonally dominant because

|c_{11}|\geq |c_{12}|+|c_{13}|

since

|-4|>|+2|+|+1|

|c_{22}|\geq |c_{21}|+|c_{23}|

since

|+6|>|+1|+|+2|

|c_{33}|\geq |c_{31}|+|c_{32}|

since

|+5|>|+1|+|-2|

Applications and properties

A strictly diagonally dominant matrix (or an irreducibly diagonally dominant matrix^[2]) is non-singular. This result is known as the Levy–Desplanques theorem.^[3] This can be proved, for strictly diagonal dominant matrices, using the Gershgorin circle theorem.

A Hermitian diagonally dominant matrix $A$ with real non-negative diagonal entries is positive semidefinite.

Proof: Let the diagonal matrix $D$ contain the diagonal entries of $A$ . Connect $A$ and $D+I$ via a segment of matrices $M(t)=(1-t)(D+I)+tA$ . This segment consists of strictly diagonally dominant (thus nonsingular) matrices, except maybe for $A$ . This shows that $\mathrm {det} (A)\geq 0$ . Applying this argument to the principal minors of $A$ , the positive semidefiniteness follows by Sylvester's criterion.

If the symmetry requirement is eliminated, such a matrix is not necessarily positive semidefinite. For example, consider

{\begin{pmatrix}-2&2&1\end{pmatrix}}{\begin{pmatrix}1&1&0\\1&1&0\\1&0&1\end{pmatrix}}{\begin{pmatrix}-2\\2\\1\end{pmatrix}}<0.

However, the real parts of its eigenvalues remain non-negative by the Gershgorin circle theorem.

Similarly, an Hermitian strictly diagonally dominant matrix with real positive diagonal entries is positive definite, as it equals to the sum of some Hermitian diagonally dominant matrix $A$ with real non-negative diagonal entries (which is positive semidefinite) and $xI$ for some positive real number $x$ (which is positive definite).

No (partial) pivoting is necessary for a strictly column diagonally dominant matrix when performing Gaussian elimination (LU factorization).

The Jacobi and Gauss–Seidel methods for solving a linear system converge if the matrix is strictly (or irreducibly) diagonally dominant.

Many matrices that arise in finite element methods are diagonally dominant.

A slight variation on the idea of diagonal dominance is used to prove that the pairing on diagrams without loops in the Temperley–Lieb algebra is nondegenerate.^[4] For a matrix with polynomial entries, one sensible definition of diagonal dominance is if the highest power of $q$ appearing in each row appears only on the diagonal. (The evaluations of such a matrix at large values of $q$ are diagonally dominant in the above sense.)

Notes

↑ For instance, Horn and Johnson (1985, p. 349) use it to mean weak diagonal dominance.
↑ Horn and Johnson, Thm 6.2.27.
↑ Horn and Johnson, Thm 6.1.10. This result has been independently rediscovered dozens of times. A few notable ones are Lévy (1881), Desplanques (1886), Minkowski (1900), Hadamard (1903), Schur, Markov (1908), Rohrbach (1931), Gershgorin (1931), Artin (1932), Ostrowski (1937), and Furtwängler (1936). For a history of this "recurring theorem" see: Taussky, Olga (1949). "A recurring theorem on determinants". American Mathematical Monthly. The American Mathematical Monthly, Vol. 56, No. 10. 56 (10): 672–676. doi:10.2307/2305561. JSTOR 2305561. Another useful history is in: Schneider, Hans (1977). "Olga Taussky-Todd's influence on matrix theory and matrix theorists". Linear and Multilinear Algebra. 5 (3): 197–224. doi:10.1080/03081087708817197.
↑ K.H. Ko and L. Smolinski (1991). "A combinatorial matrix in 3-manifold theory". Pacific J. Math. 149: 319–336.

References

Gene H. Golub & Charles F. Van Loan. Matrix Computations, 1996. ISBN 0-8018-5414-8
Roger A. Horn & Charles R. Johnson. Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2 (paperback).

External links

Numerical linear algebra

Key concepts	Floating point Numerical stability

Problems	Matrix multiplication (algorithms) Matrix decompositions Linear equations Sparse problems

Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing

Software	BLAS Specialized libraries General purpose software

Matrix classes

Explicitly constrained entries	(0,1) Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Binary Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Markov Metzler Monomial Moore Nonnegative Partitioned Parisi Pentadiagonal Permutation Persymmetric Polynomial Positive Quaternionic Sign Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Unitary Vandermonde Walsh Z

Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero

Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Diagonalizable Hurwitz Positive-definite Stability Stieltjes

Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Orthonormal Singular Unimodular Unipotent Totally unimodular Weighing

With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Coxeter Derogatory Distance Duplication Elimination Euclidean distance Fundamental (linear differential equation) Generator Gramian Hessian Householder Jacobian Moment Payoff Pick Random Rotation Seifert Shear Similarity Symplectic Totally positive Transformation Wedderburn X–Y–Z

Used in statistics	Bernoulli Centering Correlation Covariance Dispersion Doubly stochastic Fisher information Hat Precision Stochastic Transition

Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Skew-adjacency Tutte

Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)

Related terms	Jordan canonical form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Quaternionic matrix Row echelon form Wronskian

List of matrices Category:Matrices

This article is issued from Wikipedia - version of the 11/16/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.