Resolution of the symmetric nonnegative inverse eigenvalue problem for matrices subordinate to a bipartite graph (Q702032)

Given an undirected graph \(G\) with \(n\) nodes, an \(n\times n\) matrix \(A\) is said to be subordinate to \(G\) if \(a_{ij}\not=0\) implies that there is an edge between the nodes \(i\) and \(j\). This short paper proves for a bipartite \(G\) with matching number \(m\) that there is a symmetric nonnegative matrix subordinate to \(G\) with eigenvalues \(\lambda_1\geq\cdots\geq\lambda_n\) if and only if the inequalities \(\lambda_1+\lambda_n\geq 0\), \(\lambda_2+\lambda_{n-1}\geq 0\), \(\dots\), \(\lambda_m+\lambda_{n-m+1}\geq 0\), \(\lambda_{m+1}\geq 0\), \(\dots\), \(\lambda_{n-m} \geq 0\) are satisfied. Moreover, it is shown that any symmetric nonnegative matrix \(A\) subordinate to a general undirected graph \(G\) has at least \(i(G)\) nonnegative eigenvalues, where \(i(G)\) denotes the independence number of \(G\).