Characteristic polynomial of a $2d \times 2d$ real symmetric matrix.

Question

Let $d \in \mathbb{N}_{ \geq 1}$ denote a dimension and let $p \in (0,1)$. Given the $2d \times 2d$ matrix\begin{align} A := \begin{pmatrix} p & \frac{1-p}{2d-1} & \dots & \dots & \frac{1-p}{2d-1}\\ \frac{1-p}{2d-1} & \ddots & \ddots & & \vdots \\ \vdots & \ddots&\ddots & \ddots & \vdots \\ \vdots & & \ddots & \ddots & \frac{1-p}{2d-1} \\ \frac{1-p}{2d-1} & \dots & \dots& \frac{1-p}{2d-1} & p \end{pmatrix}. \end{align} The above matrix shows up, for example, when studying certain step reinforced random walks. In words, the diagonal entries are saturated by values of $p$, whereas the lower and upper halves of the matrix $A$ all have the same entries $$ \frac{1-p}{2d-1}, $$ in particular these entries depend on the dimension $d$.

One easily verifies that

• For $d=1$, where $A$ reduces to a $2 \times 2$ matrix, the eigenvalues are $ \lambda_1 =1$ and $\lambda_2= 2p-1$.
• For $d=2$, where $A$ reduces to a $4 \times 4$ matrix, the eigenvalues are $\lambda_1=1$ and $\lambda_2=\lambda_3=\lambda_4=(4p-1)/3$.

Claim: For a general dimension $d$, the eigenvalues of $A$ are given by $\lambda_1=1$, $\lambda_2=\lambda_3= \dots = \lambda_{2d} = \frac{2dp-1}{2d-1}$.

---

Question: Is there an effective method to compute the characteristic polynomial of a "highly symmetric matrix" as given by $A$, above for a general dimension $d$?

Remarks: A proof by induction seems impossible, as when we increase the dimension, the entries of the Matrix change. On the other hand, computation by the means of Laplace expansion seem complex.

Answer 1

Proof of the claim: The matrix has the form $\frac{1-p}{2d-1}E + \frac{2dp-1}{2d-1}I_{2d}$, where $E$ is the matrix with all ones. Moreover, $E = 2dP$, where $P$ is the orthogonal projection onto $\operatorname{span}\{(1,1,\ldots,1)^T\}$. Thus $$ A = \frac{2(1-p)d}{2d-1}P + \frac{2dp-1}{2d-1}I_{2d} $$ has the set of eigenvalues \begin{align} \sigma(A) &= \left\{\frac{2(1-p)d}{2d-1}\lambda + \frac{2dp-1}{2d-1} : \lambda\in\sigma(P)\right\}\\ &= \left\{\frac{2dp-1}{2d-1},\frac{2(1-p)d}{2d-1} + \frac{2dp-1}{2d-1}\right\}\\ &= \left\{\frac{2dp-1}{2d-1},1\right\}. \end{align}

Answer 2

Hint This matrix is a rank-$1$ adjustment of a scalar matrix, that is, we can write it in the form $$A = bI + {\bf u}{\bf v}^\top$$ for some column vectors ${\bf u}, {\bf v}$. In our case, $$b = p - \frac{1 - p}{2 d - 1},$$ and we can, for example, take $${\bf u} := \frac{1 - p}{2 d - 1}\pmatrix{1\\\vdots\\1} , \qquad {\bf v} := \pmatrix{1\\\vdots\\1} .$$ The characteristic polynomial of $A$ is $$c_A(t) := \det\left[t I - (bI + {\bf u}{\bf v}^\top)\right] = \det\left[(t - b) I - {\bf u} {\bf v}^\top\right] .$$ So, (for generic values of $t$) $c_A$ is the determinant of a rank-one update of an invertible matrix whose determinant we know, which is precisely what the Matrix Determinant Lemma computes: $$\det (P + {\bf u} {\bf v}^\top) = \left(1 + {\bf v}^\top P^{-1} {\bf u}\right) \det P .$$ But $c_A$ is a polynomial in $t$ and hence continuous, so the polynomial expression given by applying this identity to our above expression for $c_A$ is valid for all $t$.