Minimum-rank matrices with prescribed graph (Q2564937)

Let \(A=(a_{i,j})\) be an \(n\times n\) real symmetric matrix. For this matrix it is defined an indirected graph \(\Gamma(A)\) on \(n\) vertices \(1,2,\dots,n\) by including the unordered pair \((i,j)\), i.e., the edge joining vertex \(i\) to vertex \(j\) in the edge set, if and only if \(a_{i,j}\neq 0\). For a given graph \(G\) on \(n\) vertices the function \(m(G)=\min\{\text{rank }A:A=A^T\) and \(\Gamma(A)=G\}\) is defined. This paper includes a study of the function \(m\) and matrices which attain the attendant minimum. In the second section of the paper, the function \(m(G)\) is researched from the standpoint of connectivity. In particular, the following propositions are proved: (1) If \(G\) is connected with \(k\) vertices, \(1\leq k\leq 2\), then \(m(G)=k-1\); (2) If \(G\) is not connected, with connected components \(G^i\), \(i=1,2,\dots,k\), then \(m(G)=m(G^1)+\cdots+m(G^k)\). (3) Suppose that \(\Gamma(A)=G\) and \(\text{rank }A=m(G)=k\). Let \(A_p\) denote the matrix obtained by deleting the \(p\)th row and column from \(A\). Then \(\text{rank }A_p=k\) or \(\text{rank }A_p=k-2\) for all \(p\), i.e., \(\text{rank }A=k-1\) is not possible. In the third section, there is considered a case where the graph \(G\) is a tree \((G=T)\). Let \(T\) be a tree on \(n\) vertices \((n\geq 3)\). Let \(p\) be a vertex of \(T\). Upon deletion of \(p\) and all edges incident to \(p\) from \(T\), one obtains an acyclic, possibly disconnected graph \(T_p=T\setminus\{p\}\). Denote the connected components of \(T_p\) by \(T^1_p,\dots,T^k_p\). If \(j\geq 2\) of the connected components are simple paths which were connected to \(p\) in \(T\) through an end point, then we call \(p\) an appropriate vertex of \(T\). It is proved that if \(T\) is a tree and \(p\) an appropriate vertex of \(T\), and \(T^1_p,\dots,T^k_p\) are the connected components of \(T_p=T\setminus\{p\}\), then \(m(T)=m(T^1_p)+\cdots+m(T^k_p)+2\). Also the following theorem is proved. Let \(T\) be a tree and \(A\) be a real symmetric matrix satisfying \(\Gamma(A)=T\) and \(\text{rank }A=m(T)\). Let \(q\) be a vertex of \(T\) with degree \(k\geq 3\). Then either \(\text{rank }A=\text{rank }A_q+2\) or there exist \(k-2\) vertices \(r\) adjacent to \(q\) such that \(\text{rank }A=\text{rank }A_r+2\).