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 where "a" denotes the entry in the "i"th row and "j"th 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. Variations. The definition in the first paragraph sums entries across each row. It is therefore sometimes called "row diagonal dominance". If one changes the definition to sum down each column, 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 is diagonally dominant because The matrix is "not" diagonally dominant because That is, the first and third rows fail to satisfy the diagonal dominance condition. The matrix is "strictly" diagonally dominant because Applications and properties. A strictly diagonally dominant matrix (or an irreducibly diagonally dominant matrix) is non-singular. This result is known as the Levy–Desplanques theorem. "Proof": Suppose that "A" is a strictly diagonally dominant matrix and formula_23 is a nonzero vector such that formula_24. Let "i" be such that formula_25 is maximum in absolute value. Then contradicting the hypothesis. A Hermitian diagonally dominant  matrix formula_27 with real non-negative diagonal entries is positive semidefinite. "Proof": Let the diagonal matrix formula_28 contain the diagonal entries of formula_27. Connect formula_27 and formula_31 via a segment of matrices formula_32. This segment consists of strictly diagonally dominant (thus nonsingular) matrices, except maybe for formula_33. This shows that formula_34. Applying this argument to the principal minors of formula_27, 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 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 formula_33 with real non-negative diagonal entries (which is positive semidefinite) and formula_38 for some positive real number formula_39 (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. For a matrix with polynomial entries, one sensible definition of diagonal dominance is if the highest power of formula_40 appearing in each row appears only on the diagonal. (The evaluations of such a matrix at large values of formula_40 are diagonally dominant in the above sense.)