Diagonally dominant matrix | EPFL Graph Search

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 aij denotes the entry in the ith row and jth column. 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. 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. The matrix is diagonally dominant because since since since . The matrix is not diagonally dominant because since since since . That is, the first and third rows fail to satisfy the diagonal dominance condition. The matrix is strictly diagonally dominant because since since since . The following results can be proved trivially from Gershgorin's circle theorem. Gershgorin's circle theorem itself has a very short proof. A strictly diagonally dominant matrix (or an irreducibly diagonally dominant matrix) is non-singular. A Hermitian diagonally dominant matrix with real non-negative diagonal entries is positive semidefinite. This follows from the eigenvalues being real, and Gershgorin's circle theorem. If the symmetry requirement is eliminated, such a matrix is not necessarily positive semidefinite.

MATHICSE Technical Report : On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Daniel Kressner, Stefano Massei, Alice Cortinovis

The problem of finding a

k\times k

submatrix of maximum volume of a matrix A is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of A. We show that such a submatrix ...

MATHICSE2019