Category talk:Combinatorial Matrix

Eigenvalues of a Combinatorial Matrix

Let $A:=xJ_n+yI_n$ be a combinatorial matrix. Let $\mathbb{F}^n$ be the set of column vectors of lenght $n$ over $\mathbb{F}$. Let $u\in \mathbb{F}^n$ be the column vector whose entries are all equal to 1. Notice that $J_nu=nu$. Furthermore, \begin{align*} Au&=(xJ_n\oplus yI_n)u\\ &=xJ_nu\oplus yI_nu\\ &=xnu\oplus yu\\ &=(xn+y)u. \end{align*}

Hence, $xn+y$ is an eigenvalue of $A$. Reducing $xJ_n$ to its RREF gives an $n\times n$ matrix whose entries $a_{1j}=1$ for $j=1,2,...,n-1,n$ and all other entries are $0$. Thus, $xJ_n$ has nullity equal to $n-1$. Denote by $K(A,y)$ the eigenspace of $A$ with respect to $y$, and let $nul(B)$ denote the null space of a matrix $B$. Notice that \begin{align*} K(A,y)&=nul(A-yIn)\\ &=nul(xJ_n). \end{align*}

Hence $K(A,y)$ has dimension $n-1$. Recall that the dimension of $K(A,y)$ is the geometric multiplicity of $y$. Denote by $k(\lambda)$ and $m(\lambda)$ the geometric multiplicity and algebraic multiplicity of an eigenvalue $\lambda$, respectively. Since $A$ is a symmetric matrix and is therefore diagonalizable, then we are forced to have $m(y)=k(y)=n-1$. Since $\sum k(\lambda_i)=n$ and $\sum m(\lambda_i)=n$ for $i=1,2,...,p-1,p$ for $p$ eigenvalues of an arbitrary matrix, then we are also forced to have $m(xn+y)=m(xn+y)=1$. Hence the only possible eigenvalues of $A$ is given by the set $S:=\{xn+y,y\}$, with multiplicities $1$ and $n-1$ respectively.

Reference: John Ben S. Temones 2020 J. Phys.: Conf. Ser. 1593 012001