Diagonally dominant matrices are required in many linear algebra algorithms such as the Gauss-Seidel algorithm.


Some matrices can be made diagonally dominant by permuting its rows and others cannot.


Given an $n$ by $n$ integer matrix $A$, what is the complexity of deciding the existence of rows permutation that results in diagonally dominant matrix? Is it NP-complete?



Diagonally dominant matrix via rows permutation
Create a bipartite graph $G$ with $2n$ vertices, say $u\_1,\ldots,u\_n, v\_1,\ldots,v\_n$, where the edge set of $G$ represents matrix entries that could potentially appear on the diagonal, if the rows of $A$ were permuted to make it diagonally dominant. In other words, the bipartite graph has an edge from $u\_i$ to $v\_j$ if and only if $|a\_{ij}| \geq \sum\_{k \neq j} |a\_{ik}|$. Observe that $G$ contains a perfect matching if and only if $A$ can be made diagonally dominant by permuting its rows. Thus, there is a polynomial-time algorithm to decide the existence of a row permutation that results in a diagonally dominant matrix. In fact, constructing the graph $G$ from the $n \times n$ matrix $A$ takes $O(n^2)$ time, and using the observation that every vertex in the set $\{u\_1,\ldots,u\_n\}$ belongs to at most two edges of $G$, it is possible to come up with an algorithm that decides in $O(n)$ time whether $G$ contains a perfect matching.


