## 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 $j$th power of the eigenvalues, i.e.,

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

$\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)$

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

### 高考数学题

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

• 255,203 hits