Archive for the 'math' Category

Bocher’s formula

A colleague of mine mentioned to me today the Bocher’s formula for computing the coefficients of the characteristic polynomial of a matrix. It seems that this formula does not appear too often in textbooks or literature. I’ll just write down the formula and the idea of a simple proof here.

Let the characteristic polynomial of a matrix A be


Then the coefficients can be computed by

To prove the formula, note that the coefficient a_j is the summation of all possible products of j eigenvalues, i.e.,

\displaystyle{a_j=(-1)^j\sum_{\{t_1\cdots t_j\}\in C_n^j}\lambda_{t_1}\cdots\lambda_{t_j},}

where C_n^j denotes the j-combination of numbers from 1 to n, and the trace of A^i is the sum of the jth power of the eigenvalues, i.e.,


In addition, we have

\displaystyle{\left(\sum_{\{t_1\cdots t_j\}\in C_n^j}\lambda_{t_1}\cdots\lambda_{t_j}\right)\left(\sum_{t_{j+1}=1}^n\lambda_{t_{j+1}}^i\right)=\sum_{\{t_1\cdots t_{j+1}\}\in C_n^{j+1}}\lambda_{t_1}\cdots\lambda_{t_j}\lambda_{t_{j+1}}^i+\sum_{\{t_1\cdots t_j\}\in C_n^j}\lambda_{t_1}\cdots\lambda_{t_{j-1}}\lambda_{t_j}^{i+1}.}

The above indicates that the first part of (-1)^ja_jtr(A^i) cancels the second part of (-1)^{j-1}a_{j-1}tr(A^{i+1}), whereas the second part of (-1)^ja_jtr(A^i) cancels the first part of (-1)^{j+1}a_{j+1}tr(A^{i-1}). The rest of proof becomes obvious now.


I got a badly conditioned matrix

A = [0.0031 1 0 0 0 0 0 0
0 0.0031 1 0 0 0 0 0
0 0 0.0031 1 0 0 0 0
0 0 0 0.0031 1 0 0 0
0 0 0 0 0.0031 1 0 0
0 0 0 0 0 0.0031 1 0
0 0 0 0 0 0 0.0031 1
0 0 0 0 0 0 0 0.0031];

Matlab says that its numeric rank is 7.

The interesting thing is that A is a Jordan block!

Simple Ways to Compute Square Root

Here are some methods to compute the square root of a positive number c. Nothing innovative; but classic.

Method 1: Taylor expansion

If c>1, then

\sqrt{c}=\sqrt{\frac{1}{1-q}}=1+\frac{1}{2}q+\frac{3}{8}q^2+\cdots+(-1)^n{-1/2 \choose n}q^n+\cdots

If c<1, then

\sqrt{c}=\sqrt{1-q}=1-\frac{1}{2}q+\frac{3}{8}q^2+\cdots+(-1)^n{1/2 \choose n}q^n+\cdots

Convergence: linear.

Method 2: Fixed point iteration


Convergence: quadratic.

Method 3: Fixed point iteration


Convergence: cubic.

Criticism to the Book `Numerical Recipes’

Why not use Numerical Recipes?

Alternatives to Numerical Recipes

Top 10 Algorithms in the 20th Century

Too late to know this nice article. Well, but not too late… In the year 2000, I didn’t know any piece of the cake..

When AB=BA?

If two matrices are both diagonalizable, they commute iff they can be simultaneously diagonalized.

对于那些经常问什么时候 AB=BA 的人,这个答案满意不?



1) Write the law of cosines.
2) Is the function x-|x|^3 differentiable at the origin?
3) Draw the graph of y=2|x|^{-1}.

1) Which of the following two number is larger, 413^{1/3} or 6+3^{1/3}?
2) Find the integer solutions to the equation x^y=y^x.
3) Prove that a convex polygon of surface area equal to 1 contains a triangle of surface area equal to 1/4.




Blog Stats

  • 255,203 hits