Show that $\theta I -A$ is positive semidefinite matrix.

Question

Let $X$ be a graph with a maximum non-zero eigenvalue $\theta$, and let $A=A(X)$ be the adjacency matrix of the graph. Is it true that $\theta I -A$ is a positive semidefinite matrix?

Answer 1

Here's a hint: If $X$ is an undirected graph on $n$ vertices then $A$ is an $n\times n$ symmetric matrix. Hence $A$ is orthogonally diagonalizable, i.e., there exists an orthogonal matrix $Q$ and a diagonal matrix $D$ of real eigenvalues of $A$ such that $A = QDQ^T$. In particular, any vector in $x\in\mathbb{R}^n$ can be written as $x = Qy$.

Just as an aside, the matrix you have here is quite interesting. If by largest nonzero eigenvalue you mean the spectral radius, then $\theta I - A$ is called a singular M-matrix. M-matrices in general have a number of interesting properties, for example, inverse positivity, and they arise in such areas as the solution of differential equations and the study of Markov chains.