Matrix decomposition the other way

Question

First of all, this is no useful way to decompose a matrix - you need to know the eigenvalues beforehand. But it popped up naturally during my knot theory dabblings.

Assume that you know the characteristic equation
$$\prod_{i=1}^n (S - e_i I) = 0$$ with $S$ being an $n \times n$ matrix, $I$ the $n \times n$ identity matrix and $e_1, e_2, \dotsc$ the eigenvalues of $S$. Define the matrices
$$T_i = \prod_{j \neq i} \frac{1}{e_i-e_j} (S - e_j I)$$
Now $T_i T_j=0$ if $i \neq j$ (obvious) and $T_i.T_i=T_i$ (needs proof), to the effect that you can compute
$$S^k = \sum_{i=1}^n e_i^k T_i$$ for any $k$ (obvious again).

Question: Under what conditions does this scheme work? Equal eigenvalues are no problem, this just reduces the number of $T_i$ needed, but I've got a hunch that equal eigenvalues which are defective (off-diagonal elements in the Jordan decomposition) will be ruinous. (An elegant proof of $T_i.T_i=T_i$ is also welcome, but on gunpoint I'll probably come up with one myself :-)

Answer 1

This is a fairly standard result in the theory of diagonalizable linear operators, sometimes known as the spectral decomposition theorem for diagonalizable operators. Indeed, a linear operator over some field is diagonalizable if and only if it has a decomposition of this form. You can read about this in Hoffman & Kunze's "Linear Algebra" (specifically, the chapter "invariant sum decompositions"). The following theorem (quoted from the book) sums most of it up:

Let $T$ be a linear operator on a finite-dimensional space $V$. If $T$ is diagonalizable and if $c_1,\dots,c_k$ are the distinct eigenvalues of $T$, then there exist linear operators $E_1,\dots,E_k$ on $V$ such that:

1. $T = c_1 E_1 + \cdots + c_k E_k$
2. $I = E_1 + \cdots + E_k$
3. $E_i E_j = 0$ if $i \ne j$.
4. $E_i ^2 = E_i$ for all $i$.
5. The image of $E_i$ is the space of $T$-eigenvectors with eigenvalue $c_i$.

Conversely,if there exist $k$ distinct scalars $c_1,\dots,c_k$ and $k$ non-zero linear operators $E_1,\dots,E_k$ which satisfy conditions 1,2,3, then $T$ is diagonalizable, $c_1,\dots,c_k$ are the distinct eigenvalues of $T$ and conditions 4,5 are satisfied also.

Note that given such a decomposition for $T$, we have $f(T) = \sum f(c_i) E_i$ for any polynomial $f$ over the field. Fix some $1 \le i \le k$ and consider the polynomial $f (x) = \prod_{j \ne i} \frac{x - c_j}{c_i - c_j}$. This polynomial satisfies $f(c_r) = \delta_{r,i}$ and thus $f(T) = E_i$. So the projections $E_i$ are necessarily of the form you found.

By standard theory, $T$ is diagonalizable if and only if its minimal polynomial factors into distinct linear factors. Now, one may ask what kind of decomposition we can get if the minimal polynomial of $T$ factors into linear factors, not necessarily distinct. In this case, one can still form the sum $c_1 E_1 + \cdots + c_k E_k$ (where the $E_i$ are defined either by your formula or by property 5 above), but it won't be equal to $T$. Rather, it will differ from $T$ by a nilpotent operator (an operator $N$ with $N^m = 0$ for some integer $m$). More generally, a linear operator on a fin. dimensional vector space, over an algebraically closed field, can be written uniquely as the sum of a diagonalizable operator (called its diagonalizable part) and a nilpotent operator (called its nilpotent part) which commute with with one another. In this case $c_1 E_1 + \cdots + c_k E_k$ gives the diagonalizable part of $T$.

If the field is not algebraically closed then one may not be able to form the sum $c_1 E_1 + \cdots + c_k E_k$ at all, since some of the eigenvalues of $T$ may not be in the field. Nevertheless, there is still an analogous decomposition for $T$ in this case (at least when the field has characteristic zero, I guess), which represents $T$ (uniquely) as the sum of a "semisimple" operator and a nilpotent operator which commute with one another. Here "semisimple" is a property of operators which is equivalent to being diagonalizable if the field is algebraically closed, but is otherwise more involved.

Answer 2

The decomposition should work if and only if the minimal polynomial of the matrix can be factored into pairwise non-proportional linear factors.

Let me tell you how algebraists think about this (depending on your background, you might find everything here trivial): You have a matrix $S\in\mathrm{M}_n\left(k\right)$, where $k$ is a field. Let $m\in k\left[X\right]$ be the minimal polynomial of $S$. Then, the $k$-algebra $k\left[S\right]$ (this is the $k$-subalgebra of $\mathrm{M}_n\left(k\right)$ generated by $S$) is isomorphic to the $k$-algebra $k\left[X\right] / \left(m\right)$. (Here, $\left(m\right)$ denotes the ideal of $k\left[X\right]$ generated by $m$. As much as I dislike this notation, it is short.)

Now assume that $m$ can be factored into pairwise non-proportional linear factors, i. e. that we have $m=\lambda p_1p_2...p_u$ for some $\lambda\in k$ and some pairwise non-proportional linear polynomials $p_1,p_2,...,p_u$. Then,

$k\left[X\right] / \left(m\right) = k\left[X\right] / \left(p_1p_2...p_u\right)$

$\cong \left(k\left[X\right] / \left(p_1\right)\right) \times \left(k\left[X\right] / \left(p_2\right)\right) \times ... \times \left(k\left[X\right] / \left(p_u\right)\right)$

(where $\times$ means the direct product of $k$-algebras) by the Chinese Remainder Theorem for $k$-algebras. Each $k\left[X\right] / \left(p_i\right)$ is isomorphic to $k$ (because $p_i$ is linear), so that you obtain

$k\left[X\right] / \left(m\right) \cong k \times k \times ... \times k$ (with $u$ times $k$).

Together with $k\left[S\right] \cong k\left[X\right] / \left(m\right)$, this leads to

$k\left[S\right] \cong k \times k \times ... \times k$.

Now, for every $i$, the element $\left(0,0,...,0,1,0,0,...,0\right)$ (with $1$ on the $i$'th place, and $0$ on every other place) of $k \times k \times ... \times k$ corresponds to your $T_i\in k\left[S\right]$ under this isomorphism. Your construction of $T_i$ is pretty much equivalent to the standard constructive proof of the Chinese Remainder Theorem.

On the other hand, if $m$ cannot be factored into pairwise non-proportional linear factors, then $k\left[S\right]$ is not isomorphic to $k \times k \times ... \times k$. However, if $m$ can be factored into linear factors (for example, this happens if $k$ is algebraically closed), then at least it is isomorphic to a direct product of $k$-algebras isomorphic to $k\left[X\right] / \left(X^d\right)$ for various $d$ (each of these $k$-algebras corresponds to a Jordan block of $S$, so you still have elements like $\left(0,0,...,0,1,0,0,...,0\right)$, but they should not be as simple as your $T_i$ anymore, and they do not linearly span that direct product, so you shouldn't expect a formula as simple as $S^k = \sum_i T_i\cdot\left( \text{some constant}\right)^k$ to hold.

Answer 3

I have just seen Darij Grinberg's answer appear as I was writing, but let me give a slightly different (but closely related) perspective.

I find your text difficult to read-(note added later:before real latex inserted)-but I think you have rediscovered a standard way to diagonalise a semisimple matrix. You are implicitly assuming that $S$ has distinct eigenvalues. It's also related to how to invert a Van der Monde Matrix, and to Lagrange interpolation. I like to think of it this way. Let $A$ be a cyclic finite dimensional algebra over a field $F$, generated by an element $T$, which has minimum polynomial $p(x) = \prod_{i=1}^{n}(x-\lambda_{i})$, where the $\lambda_i$ are distinct elements of $F$. Hence $A$ has dimension $n$, and has an $F$-basis $\{I,T,\ldots,T^{n-1} \}.$ There are $n$ different non-zero algebra homomorphisms from $A$ to $F$, say $\{\mu_i : 1 \leq i \leq n \}$, where $T\mu_i = \lambda_i$ and $I\mu_i = 1$ for each $i$.

This gives an algebra homomorphism from $A$ to $F \times F \ldots \times F$ (n copies), which is an isomorphism by dimension. Hence the algebra $A$ is commutative semisimple, since any nilpotent element is sent to zero by each $\mu_i$, so must be zero. Furthermore, for each $i$, the element $$E_i = \prod_{j \neq i} \frac{T - \lambda_{j}I}{\lambda_{i} - \lambda_{j}}$$ clearly has` $E_{i}\mu_{j} = \delta_{ij}$ for $1 \leq j \leq n.$ Hence $E_{i}^{2}-E_{i}$ is annihilated by each $\mu_{j}$, so is zero, and each $E_{i}$ is idempotent.

The connection with inverting a Van der Monde matrix is as follows: evaluating the linear characters at powers of $T$ shows that for $0 \leq i \leq n-1$, we have: $T^{i} = \sum_{j=1}^{n} \lambda_{j}^{i} E_{j}.$. This shows that the matrix of coefficients to express the basis $\{T^{i}: 0 \leq i \leq n-1 \}$ in terms of the basis $\{E_{i} : 1 \leq i \leq n\}$ is the Van der Monde matrix associated to $\{\lambda_{1}, \ldots \lambda_{n}\}$. The matrix of coefficients needed to express the basis $\{E_{i} : 1 \leq i \leq n\}$ in terms of the basis $\{T^{i}: 0 \leq i \leq n-1 \}$ is therefore the inverse of that Van der Monde matrix. But this matrix can be easily read from the expressions $$E_i = \prod_{j \neq i} \frac{T - \lambda_{j}I}{\lambda_{i} - \lambda_{j}}$$ for $1 \leq i \leq n$.

Your argument (as it stands) will fail if the matrix $S$ has a minimum polynomial which is not multiplicity free. This corresponds the the fact that the cyclic $F$-algebra $A$, generated by an element $T$ with the same minimum polynomial as $S$ (assuming $F$ contains all roots of this polynomial) is no longer a commutative semi-simple algebra. This can be seen directly, since if the distinct roots of the minimum polynomial are $\lambda_1,\ldots \lambda_m$, then $\prod_{i=1}^{m} (T-\lambda_{i}I)$ is non-zero by hypothesis, but is clearly nilpotent.