Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$$ Product[1<=i<=n,(S-I*ei)]=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)$$
Ti=Product[1<=j<=n,i<>j,(S-I*ej)/(ei-ej)].
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$$ S^k=Sum(1<=i<=n,Ti*ei^k)
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 :-)

share|improve this question
2  
(you can type in LaTeX formulas directly in your question) –  Qfwfq May 18 '11 at 14:16
1  
I don't think you can call both the size of the matrix and the number of eigenvalues $n$. This would mean that you count eigenvalues with multiplicities, but then you get in troubles with equal eigenvalues: If you have a matrix with all $e_i$ equal, then all $T_i$ must be zero (since $T_iT_i=T_i$ and $T_iT_j=0$ for $i\neq j$), which means that $S^k=\sum T_ie_i^k$ cannot hold... I think this problem makes a positive answer impossible. –  darij grinberg May 18 '11 at 14:30
    
And if you don't count eigenvalues with multiplicities, I think you still get in troubles with Jordan blocks. Imagine a matrix which consists of one big Jordan block. So there is only one $e_i$, and thus there is only one $T_i$ and that is $1$. But $S^k$ can be quite complicated. So a representation like $S^k=\sum T_ie_i^k$ must fail. –  darij grinberg May 18 '11 at 14:33
    
In the diagonalizable case, isn't this equivalent to the decomposition $S=\sum \lambda_i u_i v_i^T$, where $u_i$ and $v_i^T$ are the right and left eigenvalues? It should be, otherwise I cannot imagine an explanation why your formula for the powers of $S$ work. If this is the case, you can find a generalization only if you allow terms of the form $u_iv_{i+1}^T$: you get one by considering the Jordan form and breaking it down into a sum of dyads. –  Federico Poloni May 18 '11 at 14:59
    
Hauke: I've tried to render the formulas into latex, but I've left the originals in cases where I was not entirely certain my rendering was appropriate. Please feel free to edit this however you like, or roll it back if you don't like it at all. –  Charles Staats May 18 '11 at 16:52
add comment

3 Answers

up vote 2 down vote accepted

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 satisfies also.conditions 4,5 are satisfies 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.

share|improve this answer
    
@Charles - I know I could LaTeX here...but I can't LaTeX :-) THX. @Geoff - "Looks like Langrange interpolation" was my thought also. @Darij - using the same "n" for dimension and sum was unfortunate, since if I have an (not defective!) eigenvalue of multiplicity m>1, I simply throw them together in one of the T_i. @Mark - could you compute an actual example (the horror of any true mathematician :-) with a defective eigenvalue involved? Lets say, to keep it simple and already in Jordan form 110000 011000 001000 000110 000010 000001 - how does the decomposition look? –  Hauke Reddmann May 19 '11 at 14:46
    
Hauke: In this case it's as simple as it can be: your matrix (which I shall denote $A$) has just one eigenvalue $c_1 = 1$ with multiplicity 6, so the formula for $E_1$ ($T_1$ in your post) is to be interpreted as an empty product and gives the identity operator/matrix $I=I_{6 \times 6}$. Obviously $A \ne I$ but $A-I$ is a nilpotent matrix (and a very simple one, one might add) and you get the decomposition I mentioned. One can also arrive at this by using the uniqueness of the decomposition, since $I$ is clearly diagonalizable, $A-I$ is clearly nilpotent and of course they commute. –  Mark May 19 '11 at 15:36
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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