Strongly diagonal dominant matrices

Abstract

An n ⋅ n matrix A is said to be strongly 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 and the magnitude of the diagonal entry in a column is larger than or equal to the sum of the magnitudes of all the other (non-diagonal) entries in that column. Given a matrix A we show how a strongly diagonally dominant matrix B can be computed in O(n²) time so that the distance between A and B is minimum (the distance is measured using l₁norm), i.e., the sum of differences between A and B is minimum.