## 2009年5月24日 星期日

Recently I heard two related problems about countability. They should be good exercises for mathematial analysis amateur.

Below N denotes the set of natural numbers.

The first question is, is there exists an uncountable collection of finite subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?

The second question is, is there exists an uncountable collection of subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?

------

The first question is very easy. The second question is a bit tricky.

## 2009年5月11日 星期一

### Some linear algebra

These days some of my friends discussed some linear algebra problems with me. I found them quite interesting, so let me post some of them here.

1. If A and B are square matrices of the same size, then the spectrums of AB and BA are the same. More precisely, the generalized eigenvalues of AB and BA over the complex numbers occur with the same multiplicity. This is clear when A is invertible, because then AB and BA are similar. If A is not invertible, then we can approximate A by invertible matrices. The spectrum of AB is just the zeroes of det(xI-AB) (counted with multiplicities). The claim then follows easily. This generalizes the fact that the traces and determinants of AB and BA are the same.

2. If A and B are real square matrices of the same size and if there is a complex matrix U such that $A = U^{-1} B U$, then there is a real matrix M such that $A = M^{-1} B M$. In other words, if two real matrices are similar over the complex numbers, then they are similar over the reals. Proof: Look at the equation MA = BM, where M is a square matrix of the same size as A and B. This is a linear system of equations in the entries of M with real coefficients. Hence if S_c is the complex vector space of complex matrices that satisfy this equation and S_r is the real vector space of real matrices that satisfy the same equation, then the complex dimension of S_c is the same as the real dimension of S_r. Now by assumption this dimension is at least 1. We want to find a real matrix in S_r that is invertible. Let $M_1, \dots, M_k$ be a basis of S_r over the reals. Then this is also a basis of S_c over the complex. By assumption there is a linear combination $z_1M_1 + \dots + z_kM_k$ over the complex numbers whose determinant is non-zero. Hence the polynomial $det(z_1M_1 + \dots + z_kM_k)$ in $z_1, \dots, z_k$ does not vanish identically over $\mathbb{C}^k$. It follows that this polynomial cannot vanish identically over $\mathbb{R}^k$. Hence there is a real linear combination of $M_1, \dots, M_k$ that is invertible. This finishes the proof.

3. This is more or less for my own benefit, to recall the following proof of the well-known fact that any normal matrix is diagonalizable over C. Key: Assume A is normal, i.e. A commutes with A*. Then if x is an eigenvector of A, x is also an eigenvector of A*. In fact if Ax = tx, then
$0 = \langle(A-tI)x, (A-tI)x\rangle = \langle(A^*-\overline{t} I)x, (A^*-\overline{t} I) x\rangle$
when A commutes with A*. This allows us to proceed by induction on the dimension of the vector space: first pick any eigenvector x of A. Then its orthogonal complement is preserved by A, because x is also an eigenvector of A*. Hence we can reduce to one dimension lower, and by induction this completes the proof.

## 2009年5月1日 星期五

### 一道組合題－－題解

這是上文提到的組合數學題題解。

若小方塊是橫放的，我們設它蓋著 kk + 1。這個小方格蓋著的數字的積是 k(k + 1)，不難驗算它和 0.5[k2 + (k + 1)2] - 0.5 等價。

若小方塊是縱放的，我們設它蓋著 kk + 10。這個小方格蓋著的數字的積是 k(k + 10)，不難驗算它和 0.5[k2 + (k + 10)2] - 50 等價。

假設 n 個小方塊是橫放的，50 − n 個小方塊是直放的。當我們把這 50 個積加起來時，不難發現我們必定把 0.5 × 12、0.5 × 22、0.5 × 32、……、0.5 × 1002 都在藍色的部分加了一次，而綠色的部分則為 n 個 -0.5 及 (50 - n) 個 -50。我們注意 n 的值不影響前半部分，只影響後半部分的和。因此，為使這個和盡量大，我們應使後半部分盡量大。不難得知當 n 是 50 時，這個和便達到最大值 0.5(12 + 22 + ... + 1002) - 50 × 0.5 = 169150；同理，當 n 是 0 時，這個和便達到最小值 0.5(12 + 22 + ... + 1002) - 50 × 50 = 166675。因為我們可用 50 個橫放的小方格或 50 個直放的小方格蓋著方格表，所以這兩個值都是可取的。

由上述討論可知，我們只需知道橫放的小方塊的數量，便可求得該和。我們可由填色的方法證明，橫放的小方塊的數量必定是在 0 至 50 之間的共 26 個偶數。因此這個和共有 26 個可能值。