# Calculating a determinant

How do I calculate the determinant of the following matrix: $$\begin{matrix} -1 & 1 & 1 &\cdots & 1 \\ 1 & -1 &1 &\cdots &1 \\ 1 & 1 & -1 &\cdots &1\\ \vdots & \vdots & \vdots& \ddots &\vdots \\ 1&1&1&\cdots&-1\\ \end{matrix}$$

-
Have you worked it out for small values of the dimension of the matrix? Maybe you can spot a pattern and then prove the pattern holds in general using induction. – Dan Rust Nov 4 '13 at 16:41

Hint:

Assuming your matrix is a square $n \times n$ matrix, use induction on $n$.

Start with $n = 1$ as your base case, and explore matrices of dimension $n = 2, n = 3, \ldots,$ until you notice a pattern. Then using whatever pattern you suspect (with the determinant as an expression involving $n$) as your inductive hypothesis, prove the pattern holds for an $(n+1) \times (n + 1)$ matrix.

Note: you may have to consider $n$ even and $n$ odd, separately.

-
Could use another UV +1 – Amzoti Nov 5 '13 at 2:29

Recall the formula for the determinant of a matrix $A$ $$\det(A) = \sum_{\pi\in S_n} \sigma(\pi) \prod_{i=1}^n A_{i,\pi(i)}.$$ Now the sign $\sigma(\pi)$ of a permutation $\pi$ is given by $$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$$ where the product is over the cycles of the disjoint cycle composition of $n.$ We will thus be able to evaluate the determinant if we can construct a generating function of the set of permutations where we mark the length $|c|$ of every cycle with $|c|-1$ in one variable (call it $u$) and the number of fixed points with another (call it $v$, this will count the number of elements equal to $-1$ in the product $\prod_{i=1}^n A_{i,\pi(i)}$ because they lie on the main diagonal, i.e. correspond to fixed points).

This gives the combinatorial species $$\mathcal{Q} = \mathfrak{P}(\mathcal{V}\mathfrak{C}_1(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_2(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_3(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_4(\mathcal{Z}) +\cdots).$$ which in turn produces the generating function $$Q(z,u,v) = \exp\left(vz + u\frac{z^2}{2} + u^2\frac{z^3}{3} + u^3\frac{z^4}{4}+\cdots\right).$$ This is $$Q(z,u,v) = \exp\left(vz - z + \frac{z}{1} + u\frac{z^2}{2} + u^2\frac{z^3}{3} + u^3\frac{z^4}{4}+\cdots\right) \\ = \exp\left(vz - z + \frac{1}{u}\left(u\frac{z}{1} + u^2\frac{z^2}{2} + u^3\frac{z^3}{3} + u^3\frac{z^4}{4}+\cdots\right)\right)\\ = \exp\left(vz - z + \frac{1}{u}\log\frac{1}{1-uz}\right) = \exp\left(vz - z \right)\left(\frac{1}{1-uz}\right)^{1/u}.$$ Now the term $q \times u^k v^m z^n / n!$ appearing in $Q(z,u,v)$ represents $q$ permutations that have $m$ fixed points and where $$\sum_{c\in\pi} (|c|-1) = k.$$ Furthermore for all these permutations we have that $$\sigma(\pi)\prod_{i=1}^n A_{i,\pi(i)} = (-1)^k (-1)^m.$$ This implies that $$\det(A) = n! [z^n] Q(z,-1,-1) = n! [z^n] \exp\left(-z - z \right)\left(\frac{1}{1+z}\right)^{-1}\\ = n! [z^n] \exp(-2z) (1+z) = n! ([z^n] \exp(-2z) + [z^{n-1}] \exp(-2z)) \\= n! \left(\frac{(-2)^n}{n!} + \frac{(-2)^{n-1}}{(n-1)!}\right) = (-2)^{n-1} (-2 + n) \\ = (n-2) (-2)^{n-1}.$$

-