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

\displaystyle{p(\lambda)=\lambda^n+a_1\lambda^{n-1}+\cdots+a_n.}

Then the coefficients can be computed by
a_1=-tr(A),
a_2=-\frac{1}{2}\left(a_1tr(A)+tr(A^2)\right),
a_3=-\frac{1}{3}\left(a_2tr(A)+a_1tr(A^2)+tr(A^3)\right),
\vdots
a_n=-\frac{1}{n}\left(a_{n-1}tr(A)+\cdots+a_1tr(A^{n-1})+tr(A^n)\right).

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.,

\displaystyle{tr(A^i)=\sum_{t=1}^n\lambda_t^i.}

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

x_{n+1}\leftarrow\frac{1}{2}\left(x_n+\frac{c}{x_n}\right)

Convergence: quadratic.

Method 3: Fixed point iteration

x_{n+1}\leftarrow\dfrac{x_n(x_n^2+3c)}{3x_n^2+c}

Convergence: cubic.

Criticism to the Book `Numerical Recipes’

Why not use Numerical Recipes?

http://math.stanford.edu/~lekheng/courses/302/wnnr/nr.html

Alternatives to Numerical Recipes

http://math.stanford.edu/~lekheng/courses/302/wnnr/nr-alt.html

Top 10 Algorithms in the 20th Century

http://www.siam.org/news/news.php?id=637

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 的人,这个答案满意不?

高考数学题

下面是莫斯科大学1978年对非尤太人和尤太人的入学考试试题:

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.

中国某年高考题
chinese.gif

英国高校新生摸底考试题
english.gif


Categories

Blog Stats

  • 246,614 hits