Determinant of the following $(n\times n)$ matrix

How does one compute the determinant of the following $(n\times n)$ matrix \begin{pmatrix} x & 1 & \cdots & \cdots & 1 \\ 1 & x & \ddots & & \vdots \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ \vdots & & \ddots & x & 1 \\ 1 & \cdots & \cdots & 1 & x \\ \end{pmatrix} for x $\in Q$ and where every off-diagonal element is $1$?

My thoughts:

• Rule of Sarrus won't help us, because it only works for $(3\times 3)$ matrices

• Using Laplace's formula doesn't seem to be helpful in this case, since we don't even know which value $n$ will have

Help is appreciated!

• Are the 1s everywhere except the diagonal, or just on the boundaries? – David G. Stork Jan 13 '16 at 22:41
• everywhere except the diagonal :) – steve2557 Jan 13 '16 at 22:51
• Hint: The $n \times n$ matrix $J_{n}$ with every entry $1$ has the eigenvalue $n$ with multiplicity $1$ and the eigenvalue $0$ with multiplicity $n-1$ (can you see why, or at least verify it)?. Your matrix is $(x-1)I_{n} + J_{n}$. – Geoff Robinson Jan 13 '16 at 22:51

Assuming your matrix has $1$s everywhere except the diagonal, then we can write your matrix ${\bf M} = (x-1) {\bf I}_{n \times n} + {\bf 1}_n \times {\bf 1}_n$, where ${\bf I}$ is the identity matrix and ${\bf 1}_n$ a vector of $1$s.
${\rm det}({\bf I}_n + {\bf c}^t {\bf r}) = 1 + {\bf r}^t {\bf c}$
Plugging in, noting ${\bf 1}_n^t {\bf 1}_n = n$, that ${\rm det}[a\ {\bf I}_{n \times n}] = a^n$ for scalar $a$, and counting multiplicities and factors we get $(x-1)^{n-1}(x+n-1)$.
Consider the matrix $I-J,$ where $J$ is the all ones matrix. Then the determinant of the matrix $xI - (I-J)$ is the characteristic polynomial of $I-J,$ so it suffices to find the eigenvalues of $I-J.$ Since $J$ is rank $1,$ $0$ is an eigenvalue of multiplicity $n-1,$ and it's clear that $n$ is the remaining eigenvalue. Hence the eigenvalues of $I-J$ are $1$ of multiplicity $n-1$ and $1-n$ of multiplicity $1,$ whence the desired expression is just $(x-1)^{n-1}(x+n-1).$
Let $\omega$ be a primitive $n$-th root of unity. It's a special type of circulant matrix with associated polynomial $$f(t)=x+t+t^2+\cdots+t^{n-1}\\ \therefore \det=\prod_{j=0}^{n-1}f(\omega^j)=f(1)\prod_{j=1}^{n-1}(x-1)=(x-1)^{n-1}(x+n-1)$$