2
$\begingroup$

A complete graph of $n$ nodes has an $n$x$n$ adjacency matrix $A_{ij}$ such that $$ a_{ij} = 0 \text{, if } i = j \\ a_{ij} = 1 \text{, if } i \ne j $$ i.e. there are 0s down the diagonal and 1s everywhere else.

Given such an $n\times n$ matrix, the determinant is given by the formula $$\det\left(A_{ij}\right) = (-1)^{n-1}(n-1).$$

In general the determinant of an $n\times n$ matrix is given by $$ \det\left(A_{ij}\right) = \sum_{\sigma \in S_n}{\operatorname{sgn}(\sigma)}\prod_{i=1}^n{a_{i,\sigma_i}}. $$

How can one use the general formula to prove the formula for this specific case?

$\endgroup$

1 Answer 1

3
$\begingroup$

If $\sigma$ is a permutation, then $\prod_{i=1}^n{a_{i,\sigma_i}}=0$ if $\sigma$ has a fixed point and one otherwise. We thus have $$\det(A)= \sum_{\substack{\sigma\in\mathcal S_n \\ \sigma(i)\neq i \forall i}} \varepsilon(\sigma).$$ Define for $k \in \{1,\dots,n-1\}$ the set $I_k:=\{\sigma\in\mathcal S_n, \sigma(n)=k,\sigma(i)\neq i\forall i\}$. If $\sigma$ belongs to $I_k$, then $\pmatrix{1&k} \circ \sigma \circ \pmatrix{1&k}$ belongs to $I_1$ and has the same signature as $\sigma$. Therefore, $$\det(A)=\sum_{k=1}^{n-1}\sum_{\sigma \in I_k}\varepsilon(\sigma)= (n-1)\sum_{k\in I_1}\varepsilon(\sigma).$$ Now it remains to check that $\sum_{k\in I_1}\varepsilon(\sigma)=(-1)^{n-1}$, which can be done by induction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .