Diagonally dominant matrix

From Wikipedia, the free encyclopedia

In mathematics, a matrix is said to be diagonally dominant if in every row of the matrix, the magnitude of the diagonal entry in that row is larger than the sum of the magnitudes of all the other (non-diagonal) entries in that row. More precisely, if the entry in the ith row and jth column of a matrix is aij, and if

|a_{ii}| > \sum_{j\neq i} |a_{ij}|, \,

then the matrix is diagonally dominant.

Contents

[edit] 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.

The definition in the first paragraph uses a strict inequality. It is therefore sometimes called strict diagonal dominance. If a weak inequality (\geq) is used, this is called weak diagonal dominance.

[edit] Applications and properties

By the Gershgorin circle theorem, a strictly diagonally dominant matrix is non-singular. This result is known as the Levy–Desplanques theorem.[1]

A Hermitian diagonally dominant matrix with real non-negative diagonal entries is positive semi-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 diagonally dominant.

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

[edit] Links

[edit] Notes

  1. ^ 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 56: 672–676. 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.

[edit] References

  • Gene H. Golub & Charles F. Van Loan. Matrix Computations, 1996. ISBN 0-801-85414-8
  • Roger A. Horn & Charles R. Johnson. Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2 (paperback).
Retrieved from "http://en.wikipedia.org../../../d/i/a/Diagonally_dominant_matrix.html"