Combinatorial considerations for the number of distinct eigenvalues of a matrix

We address the inverse eigenvalue problem of determining the potential number of distinct eigenvalues of a real matrix based on the zero-nonzero structure of the matrix. In particular, a nonzero pattern $\mathcal{A}$ is a matrix with entries in $\{*,0\}$. The allow sequence of distinct eigenvalues for an $n\times n$ pattern $\mathcal{A}$ is a binary vector of length $n$ with the $k$th entry equal to $1$ if and only if there exists a real matrix with pattern $\mathcal{A}$ having exactly $k$ distinct eigenvalues. We develop digraph techniques for identifying properties of the allow sequence and give some general results for cycle patterns. We obtain a classification for all the star patterns according to their allow sequence. We also determine the allow sequence for each $n\times n$ irreducible pattern with $n\leq 4$.