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 , then there is a real matrix M such that . 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 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 over the complex numbers whose determinant is non-zero. Hence the polynomial in does not vanish identically over . It follows that this polynomial cannot vanish identically over . Hence there is a real linear combination of 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

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.

一道組合題－－題解

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

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

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

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

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

一道組合題

　　最近我從朋友口中得知一道有趣的組合題，其題解十分有趣。各位可以試試。

　　在一個 10 × 10 的方格表裏，已由上至下，由左至右順序填好 1 至 100 這 100 個整數（即第一橫行順序填好 1 至 10，第二橫行填好 11 至 20，如此類推）。現在我們用 50 個 1 × 2 的小方塊沒有重覆地蓋著這 100 個方格（縱放或橫放皆可）。蓋好後，我們將每一個小方塊蓋著的兩個數字分別乘起來，然後求這 50 個乘積的和。

問題一：這個和的最大可能值和最小可能值是甚麼？

問題二：這個和共有多少個可能值？

　　我找到了一個不消十五行的解答。這題解以不變量 (invariant) 為主要技巧。我會在 5 月 1 日公佈我的答案。

數學講座

日期：2009 年 4 月 28 日（星期二）
時間：下午 2 時 30 分至 5 時（活動包括講座及參觀）
地點：香港大學明華綜合大樓 T2 演講廳
講者：蕭文強教授
講題：Does Applied Mathematics Exist? -- A Lesson from Godfrey Harold Hardy
簡介：

A discussion of this issue would touch upon various aspects of science, involving deep and philosophical questions. With a far more modest aim and scope this talk looks at the issue through some episodes in the work of one mathematician of the last century, Godfrey Harold Hardy (1877-1947).

有關其他詳情，可瀏覽這裡。

Context Free Grammar Exercise

雖然題目是英文，但內容是中文的。因為不知道context free grammar的中文。

雖然context free grammar是計算機理論的東西，但原理其實都是數學。以下是一條典型的習題。

以下是五個規矩：

1) S -> SS
2) S -> aSbb
3) S -> bbSa
4) S -> bSaSb
5) S -> e（即empty的意思）

玩法是這樣的。舉例說，你一開始你有一個S。
你可以用 1) 變成SS。
對第一個S你可以用 2)，可變成 aSbbS 。
對上一行的第二個S用 3) ，可變成 aSbbbbSa 。
對上一行的兩個S都用 5)，可變成 abbbba 。

還有一個規矩，就是最後生成的字串是不可以有S的存在。

讀者應該不難知道所有用這五個規矩生成的字串，b的數目是a的數目的兩倍。

但問題來了。是否所有b的數目是a的數目兩倍的字串，都可使用這五個規矩生成出來？

An Exhibition about Mathematics

A few days ago I went to an exhibition called "Mathema". Below are some random pics I took at the exhibition. (Highlight the space to see the answer.)




What is the purpose of this machine?

Answer: For computing binary numbers.







Can you relate this picture to a famous parable?

Answer: "The parable of the rice grains".




What is the purpose of this machine?

Answer: The Germans used this machine for sending encrypted messages (known as the Caesar's code) during WWII. Note that the the three vertical wheels (just above the keys) will turn the keys, and they allow three degrees of freedom for doing encryption. The guide told us that the British actually broke the code during the war, as the Germans did not use the machine in a careful way. (They always begin their messages with Dear ... ==" )






Why are the above two maps different?
tance, an area r
Answer: Each of the two maps preserve a certain quantity: distance and area respectively.




These two books list out the first 4 million digits of pi!










You can "see" how the Pythagoras' Theorem works by turning the wheel!







This is what NASA sent to the space for aliens to read~



Why is this number so special?

Answer: This number is called "googol", and the name of the famous search engine "google" was inspired by it.





Along which path will a ball from the upper point reach the lower point in the least time?

Answer: Along the curve. This is the famous "Brachistochrone curve". This curve has another remarkable property: the time it takes for the ball to reach the lowest point is always the same, regardless of the starting point!








Mathematicians regard this as the most beautiful theorem in the world. This formula appears so simple but yet it involves some of the most important constants: 1, 0, e, i, pi.

小學集體回憶系列(3) 過界

「老師，佢過界！」

到底由幾時開始，你不再理會隔鄰的同學有否「過界」？

初小時是分組上堂的，六、七張桌子貼在一起成「T」字形，謂之一組。由於小學生上課太多文具、書簿了，於是就衍生了一個問題，有時你的物品會越過桌與桌之間的邊界，佔用了同學小小的空間，謂之「過界」。

被人「過界」為甚麼要立即出聲？第一，你那小小的面積被侵犯了，基於常識科/社會科中「香港地少人多、寸金尺土」的教誨，你要維護自己的重要權益；第二，你雖然不介意空間被佔，但那同學可能想試探你是否懦弱好恰，你需要向他示威；第三，那同學是異性，你不想被傳緋聞。

當你上中學、大學，雖然還是有跟同學一起坐的機會，但你實在不太在意他們有否過界。因為你已經明白，那張桌子其實不是你的。由桌子到學校、社會、世界，你只是它們的過客，你對它們既無「主權」，也無「歸屬感」可言。世故而老練的你，知道成年人反正是彼此利用，於是你不介意被人「過界」了。

如果你曾向老師投訴同學「過界」，那你當年也是一個天真無邪的小孩子。