Construct symmetric matrix with zero diagonal from given eigenvalues

Question

Is there a procedure to construct a symmetric matrix that has zeros on the diagonal and a specific set of eigenvalues? For example, for the eigenvalues $1,-1/2,-1/2$ the matrix $$ A = \left( \begin{matrix} 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 0 \end{matrix} \right) $$ exists (there are other solutions too). Is there a procedure to generate such a matrix for given eigenvalues (the sum of which is zero of course) for arbitrary matrix dimensions?

Answer 1

Since $A$ is traceless, if its diagonal is not already zero, it must possess a positive diagonal entry and a negative diagonal entry. Hence there is an index set $\mathcal I=\{i,j\}$ such that $a_{ii}a_{jj}<0$ and the principal $2\times2$ submatrix $A(\mathcal I,\mathcal I)$ is indefinite. Let $A(\mathcal I,\mathcal I)=Q\operatorname{diag}(\lambda_1,\lambda_2)Q^T$ be an orthogonal diagonalisation, where $\lambda_1>0>\lambda_2$. Now let $U$ be the orthogonal matrix obtained from the identity matrix by setting $$ U(\mathcal I,\mathcal I)=Q\pmatrix{\frac{-\sqrt{-\lambda_2}}{\sqrt{\lambda_1-\lambda_2}} &\frac{\sqrt{\lambda_1}}{\sqrt{\lambda_1-\lambda_2}}\\ \frac{\sqrt{\lambda_1}}{\sqrt{\lambda_1-\lambda_2}} &\frac{\sqrt{-\lambda_2}}{\sqrt{\lambda_1-\lambda_2}}}. $$ Then the $i$-th diagonal entry of $U^TAU$ is zero. Note that if we call $U^TAU$ the new $A$, then $A$ remains traceless and $a_{kk}$ remains unchanged for all $k\ne i,j$. So, we may proceed recursively, turn at least one nonzero diagonal entry of $A$ into zero in each iteration and leave all zero diagonal entries unchanged. In the end, we can turn the whole diagonal of $A$ into zero in at most $n-1$ iterations. Since we modify two rows and two columns in each iteration, the total complexity of this algorithm is $O(n^2)$.