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

What methods exist for finding the square-root of a non-diagonalizabe positive complex matrix?

share|improve this question
3  
If, by positive, you mean that $\langle Ax,x\rangle$ is non-negative for all vectors $x$, then the matrix is diagonalizable. So your question might need rethinking –  Yemon Choi Feb 4 '10 at 3:07
1  
For a Jordan cell $A$ with eigenvalue $t\neq 0$ write $A=tB$. $B$ has 1's on the main diagonal and $1/t$'s immediately above it. $N=B-I$ is nilpotent, so a square root $C$ of $B=I+N$ can be found using the binomial formula (which gives a finite sum). Then $\sqrt{t}C$ will be a square root of $A$. If $A$ is a Jordan $n$ by $n$ cell with eigenvalue 0, then $A$ has no square roots for $n>1$ (for rank reasons). The case when $A$ is arbitrary follows from the above. –  algori Feb 4 '10 at 3:54
1  
Wikipedia has a little section on non symmetric/hermitian positive matrices at en.wikipedia.org/wiki/… –  Mariano Suárez-Alvarez Feb 4 '10 at 3:55
1  
It should be noted that, in general, algori's procedure gives many different square roots.. –  Mariano Suárez-Alvarez Feb 4 '10 at 3:59
3  
Would someone please step up and give their comments as an answer? :) –  Pete L. Clark Feb 4 '10 at 4:14
show 10 more comments

2 Answers

Following Pete's advice, here is my comment with some more details added:

For a Jordan block $A$ with eigenvalue $t\neq 0$ write $A=tB$. $B$ has 1's on the main diagonal and $1/t$'s immediately above it. $N=B-I$ is nilpotent, so a square root $C$ of $B=I+N$ can be found using the binomial formula (which gives a finite sum). Then $\sqrt{t}C$ will be a square root of $A$.

If $A$ is arbitrary, then find the Jordan form $B$ of $A$ so that $A=C^{-1}BA$. If there are no zero eigenvalues, then we can find a square root of each block and then conjugate back.

If there are Jordan blocks with eigenvalue 0, the problem gets a bit trickier. The square of a Jordan $m$ by $m$ block with zero eigenvalue is conjugate to the union of two $m/2$ by $m/2$ blocks if $m$ is even and to the union of an $(m-1)/2$ by $(m-1)/2$ block and an $(m+1)/2$ by $(m+1)/2$ block if $m$ is odd. This allows one to compute a square root of a union of two Jordan blocks of equal sizes or of a union of an $n$ by $n$ block and an $(n+1)$ by $(n+1)$ block.

Let $a_1\leq \ldots\leq a_k$ be the sizes of the zero eigenvalue Jordan blocks (including 1 by 1 ones, so $\sum a_i$ is the dimension of the generalized eigenspace with eigenvalue 0). $A$ has a square root, iff $a_1\ldots,a_k$ can be obtained from a sequence $b_1\leq \ldots\leq b_l$ of positive integers by replacing an even $m$ with $m/2,m/2$, an odd $m$ with $(m-1)/2,(m+1)/2$ and leaving 1's untouched. (I know this looks messy but can't think of anything better.)

Of course, a square root of a matrix is not unique (if it exists).

Note that if all eigenvalues of $A$ are positive, then numerically it's probably easier to use the binomial formula straight away:

$$\sqrt{A}=\sqrt{t}(I+\frac{1}{2t}X-\frac{1}{8t^2}X^2 +\cdots).$$

Here $X=A-tI$ and the formula is valid for $t$ greater then the maximum eigenvalue of $A$.

share|improve this answer
1  
After some googling, I've found this paper: maths.manchester.ac.uk/~nareports/narep89.pdf. The paper should contain an efficient algorithm for real matrices, and references for algorithms for complex matrices. It seems to me that using a polynomial function for the square root might be inefficient (a lot of matrix multiplications). –  user2734 Feb 4 '10 at 7:45
1  
unknown -- here we have to find powers of the same matrix, not to multiply arbitrary matrices; computing powers is cheap e.g. one can find a Jordan form first (which the general method involves anyway). –  algori Feb 4 '10 at 15:03
add comment

I'm not sure if you're looking for an efficient algorithm or just a method that works. In the latter case, we can ignore the positivity condition and just look for square roots of general complex matrices. algori essentially gave the answer in the comments: if you diagonalize the matrix, the Jordan blocks with nonzero eigenvalues automatically have (nonunique) square roots.

The nilpotent Jordan blocks are a little more delicate: First, arrange them in decreasing order by size. Then in order for a square root to exist, it is necessary and sufficient that the (2n-1)st block is at most one larger than the (2n)th for all positive n. Approximate proof: If you square a nilpotent block it becomes two blocks of approximately equal size.

share|improve this answer
    
I presume sbseminar.wordpress.com/2008/12/02/… is relevant? –  Yemon Choi Feb 4 '10 at 4:49
    
Truly my finest hour... –  S. Carnahan Feb 4 '10 at 5:37
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.