MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Decomposition of Matrix to its sub-matrix with constant rank

When we study the structure of simple graphs with a lot of $1$ or $-1$ as its adjacency eigenvalues, the rank of its adjacency matrix is very important. The reason is, in these case, we can study the matrix $A+I$ and $A-I$, where $A$ is the adjacency matrix of graph $G$.

Let $A$ be a symmetric $n\times n$ matrix such that $A+I$ has rank $k$. It is obvious to see that, $A$ has $k$ eigenvalues $-1$. Since $A$ is symmetric, we can write

\begin{equation*} A+I= \begin{bmatrix} A_1& B \newline B^T& A_2 \end{bmatrix} , \end{equation*}

where $A_1$ is a $k\times k$ matrix, $B$ is $k\times (n-k)$ matrix, $B^T$ is the transpose of $B$ and $A_2$ is $(n-k)\times (n-k)$ matrix. It is easy to see that $A_1$ is nonsingular.

My question is:

1) In general, is it true that $A_2=B^TA_1^{-1}B$, and if it is true, how we can prove it? We can see that $rank(A+I)=rank(A_1)$. May be it can help for proof as a strategy.

2) Would you please give me some references for these types of relations in matrices?

For rank$(A_1)=2$ or rank$(A_1)=3$, Professor Doob and Professor Haemers showed that, the structure of $A$ are determined, equivalently, the graphs with $n$ vertices and $n-2$ or $n-3$ eigenvalues $-1$ are determined by their adjacency spectrum. The answer for $n-4$ eigenvalues equal to $-1$ is negative. My another question is:

For which integer $n-k$, where $4\leq k\leq n$, the answer is known? I mean, if the multiplicity of $-1$ for graph $G$ with $n$ vertices be $n-k$, what are the known results about cospectral mate?

Professor Doob and Haemers, gave and example for $n-4$. I found some examples in other cases. I think these examples are important. Am I thinking truly?

-

It may take some reordering of the rows (and correspondingly the columns) to make $A_1$ nonsingular.
If it is, consider $$( A+I) \pmatrix{A_1^{-1} & -A_1^{-1} B\cr 0 & I\cr} = \pmatrix{I & 0\cr B^T A_1^{-1} & A_2 - B^T A_1^{-1} B\cr}$$
If this has rank $k$, the lower right block must be $0$.