# reduced matrix will always have an eigenvector orthogonal to vector of all ones?

Suppose $G$ is a simple graph on $n$ vertices, with a vertex $w$ of degree $n-1$. $A$ is corresponding adjacency matrix. If we remove row and column corresponding to $w$, and on non digonal entries replace $0$ to $2$, is it true that reduced matrix will always have an eigenvector orthogonal to vector of all ones?

EDIT: The matrix one gets is distance matrix of graph (deleted one row and one column)

I feel it is true. I tried a few examples and it is holding good there. I have no idea how to prove it. Please help.

What is the point of the vertex $w$ of degree $n-1$? [EDIT: I see, this gives the interpretation of $M$ as the distance matrix of the original graph.] To any graph $G^{\prime}$ on $n-1$ vertices, you can add a vertex $w$ connected to everything to get a graph $G$ on $n$ vertices with this property. Better to just start with $G^{\prime}$. Then you claim the adjacency matrix $A$ (I'm already considering the row/column "removed"), if we replace all $0$ off the diagonal with a $2$, has an eigenvector orthogonal to $j$, the all one's matrix.

The matrix you are talking about can be written $M=2J-A-2I$ (where $J$ is the all-ones matrix). Your claim is that $j^{\perp}$ contains an eigenvector of $M$. Note that $\dim(j^{\perp}) = n-2$ and $M$ is a symmetric $(n-1)\times(n-1)$ matrix and so is diagonalizable; that means there is a basis for $\mathbb{R}^{n-1}$ of eigenvectors for $M$. If any eigenspace of $M$ has dimension $>1$, then this is definitely true (this eigenspace will have to intersect $j^{\perp}$ nontrivially by a dimension argument). So you if you want a counterexample, you will need to look at graphs for which $M$ has $n-1$ distinct eigenvalues (and are not regular; if the graph is regular then $M$ will have $j$ as an eigenvector, and any eigenvector for another eigenvalue will be in $j^{\perp}$).

• Thanks..You are quite right to point about $w$. I noticed it later. – rationalize Sep 7 '15 at 14:05
• " If any eigenspace of M has dimension >1, then this is definitely true " Can you elaborate please. Let $n-1=4$ and $\{(2,0,2,0), (0,2,0,2)\}$ be an eigenspace, Then it's not intersecting $j^{\perp}$. What I am missing here? – rationalize Sep 8 '15 at 5:03
• If these two are eigenvectors for the same eigenvalue, then we also have that $(2,0,2,0)-(0,2,0,2) = (2,-2,2,-2)$ is an eigenvalue (since the set of eigenvectors for a fixed eigenvalue forms a subspace; these two vectors you gave would just provide a basis for that subspace). – Morgan Rodgers Sep 8 '15 at 5:21
• Oh..I see. Thank you so much @Morgan. – rationalize Sep 8 '15 at 5:33