I need to prove that characteristic polynomial of a square matrix $A$ is $$\det(A - rI) = \prod_{i = 1}^n(r - a_{i,i}) + q(r)$$

Where $q(r)$ is a polynomial of degree less than or equal to $n - 2$ and $a_{i,j}$ are the entries of matrix $A$.

Let $B = A - rI$ with entries $b_{i,j}$, then

$$\det B = \sum_{\sigma \in \operatorname{Perm}(n)}\operatorname{sign}(\sigma) \prod_{i = 1}^n b_{\sigma(i), i} $$

For $\tau \in \operatorname{Perm}(n)$ such that $\tau(i) = i$, we have

$$\det B = \sum_{\sigma \in \operatorname{Perm}(n) - \{\tau\}}\operatorname{sign}(\sigma) \prod_{i = 1}^n b_{\sigma(i), i} + \prod_{i=1}^n b_{\tau(i), i}$$

I know $b_{i,i} = a_{i,i} - r$ so $\prod_{i=1}^n b_{\tau(i), i} = \prod_{i = 1}^n(r - a_{i,i})$.

Now I just need to prove that $ \sum_{\sigma \in \operatorname{Perm}(n) - \{\tau\}}\operatorname{sign}(\sigma) \prod_{i = 1}^n b_{\sigma(i), i}$ is a $n-2$ degree polynomial in $r$.

I can see why this statement is true; If we have $\sigma \ne \tau$, we should at least have $\sigma(k) = j$ and $\sigma (j) = k$ for $j,k \le n$. So we lose two diagonal entries in the product $\prod_{i = 1}^n b_{\sigma(i), i}$, namely $b_{j,j}$ and $b_{k,k}$. Hence the degree of $\sum ...$ is $n-2$ atmost.

However this argument is hardly rigorous, how can I make this argument rigorous ?


You are very close to a full proof, and you've stumbled upon all the right ideas. The result you want to make your argument rigorous is the following lemma.

Lemma: Let $S_n$ denote the symmetric group on $n$ letters. Let $e$ denote the identity permutation. Then any $\sigma \in S_n\backslash\{e\}$ has at most $n-2$ fixed points.

Proof: Let $\sigma \in S_n\backslash\{e\}$. Let $f_\sigma$ denote the number of fixed points of $\sigma$.

Since $\sigma$ is not the identity, it cannot fix every element, so we must have $f_\sigma < n$.

Now suppose that $f_\sigma = n-1$. Then $f_\sigma$ must fix all but one element, say $k$. Let $\sigma(k) = j$, where we have by assumption $k\neq j$. Since $k$ is the only non-fixed point, this means that $j$ must be a fixed point of $\sigma$. But this means that we have $$j=\sigma(j)= \sigma(k),$$ which contradicts the fact that $\sigma$ is a permutation, and hence a bijective map. It follows that $f_\sigma \neq n-1$ and hence we must have $f_\sigma \le n-2$. $\square$

Having this lemma should allow you to finish your proof.

  • $\begingroup$ Amazing ! Thank you very much. $\endgroup$ – user8277998 Nov 18 '17 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.