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月24日 星期日
2009年5月22日 星期五
四捨五入
日前有報章報導，東亞銀行的網上系統有漏洞，只要不斷透過四捨五入造成的誤差，便可安坐家中賺取利潤。本文談談「四捨五入」這個數學上常用的取近似值的方法。
四捨五入的原理很簡單，基本上就是「向較接近的一方取近似值，以減少誤差」。例如，要把123.456 取小數點後一位的近似值，則因為 123.456 界乎 123.4 和 123.5 之間，而且較接近後者，因此我們取 123.5 作為近似值。
這裡有一個小問題，就是「較接近的一方」並不一定存在，例如把 123.450 捨入至 123.4 和 123.5 都是「同樣接近」的，故此我們根據「五入」的規則，把 123.450 向上捨入至 123.5。但這樣做的話得出的近似值會偏大。如果只是把 123.450 變成 123.5 當然問題不大，不過如果是 1.5 變 2，或 10.5 變 11 的話，而且經常要「五入」的話（這樣的例子是存在的，例如以 0.5 分為評分單位但最終分數必定是整數的考試），那就很不同了。
為了解決這個「偏大」的問題，一個「修正版」的四捨五入法是「四捨六入五留雙（banker's rounding）」。名字本身有點誤導：雖然叫「六入」，但其實是「(5+ε)入」，例如 123.456 仍會「(5.6)入」至 123.5。只是當出現 123.450 這些「打和」的情況時，才採用「五留雙」的規則：如果 5 字前的位是雙數則保留，單數則進位，故基於「4」是雙數，123.450 會向下捨入至 123.4，而 123.550 則會上捨入至 123.6。至於「banker」是否真的採用此規則，大家不妨測試一下。
那麼為甚麼要「留雙」而不是「留單」呢？我有以下猜測。在以上 123.456 的例子中，如果採用四捨五入法取小數點後一位的近似值，則會變成 123.5，如果再把近似值取最接近整數，則變成 124。問題是最接近 123.456 的整數應是 123 才對。再細看一下，我們發現其實 123.44...445 已經可以「合法地」變成 124：只要逐位「五入」即可，而且即使採用「四捨六入五留單」，同樣的情況仍會發生。採用「五留雙」的話，這樣的情況會得到一點點的改善（雖然也好不到哪裡）：123.4500...001 才可以「合法地」變成 124！
四捨五入的原理很簡單，基本上就是「向較接近的一方取近似值，以減少誤差」。例如，要把123.456 取小數點後一位的近似值，則因為 123.456 界乎 123.4 和 123.5 之間，而且較接近後者，因此我們取 123.5 作為近似值。
這裡有一個小問題，就是「較接近的一方」並不一定存在，例如把 123.450 捨入至 123.4 和 123.5 都是「同樣接近」的，故此我們根據「五入」的規則，把 123.450 向上捨入至 123.5。但這樣做的話得出的近似值會偏大。如果只是把 123.450 變成 123.5 當然問題不大，不過如果是 1.5 變 2，或 10.5 變 11 的話，而且經常要「五入」的話（這樣的例子是存在的，例如以 0.5 分為評分單位但最終分數必定是整數的考試），那就很不同了。
為了解決這個「偏大」的問題，一個「修正版」的四捨五入法是「四捨六入五留雙（banker's rounding）」。名字本身有點誤導：雖然叫「六入」，但其實是「(5+ε)入」，例如 123.456 仍會「(5.6)入」至 123.5。只是當出現 123.450 這些「打和」的情況時，才採用「五留雙」的規則：如果 5 字前的位是雙數則保留，單數則進位，故基於「4」是雙數，123.450 會向下捨入至 123.4，而 123.550 則會上捨入至 123.6。至於「banker」是否真的採用此規則，大家不妨測試一下。
那麼為甚麼要「留雙」而不是「留單」呢？我有以下猜測。在以上 123.456 的例子中，如果採用四捨五入法取小數點後一位的近似值，則會變成 123.5，如果再把近似值取最接近整數，則變成 124。問題是最接近 123.456 的整數應是 123 才對。再細看一下，我們發現其實 123.44...445 已經可以「合法地」變成 124：只要逐位「五入」即可，而且即使採用「四捨六入五留單」，同樣的情況仍會發生。採用「五留雙」的話，這樣的情況會得到一點點的改善（雖然也好不到哪裡）：123.4500...001 才可以「合法地」變成 124！
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
, 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
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.
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
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.
2009年5月1日 星期五
一道組合題－－題解
這是上文提到的組合數學題題解。
若小方塊是橫放的，我們設它蓋著 k 和 k + 1。這個小方格蓋著的數字的積是 k(k + 1)，不難驗算它和 0.5[k2 + (k + 1)2] - 0.5 等價。
若小方塊是縱放的，我們設它蓋著 k 和 k + 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 個可能值。
若小方塊是橫放的，我們設它蓋著 k 和 k + 1。這個小方格蓋著的數字的積是 k(k + 1)，不難驗算它和 0.5[k2 + (k + 1)2] - 0.5 等價。
若小方塊是縱放的，我們設它蓋著 k 和 k + 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 個可能值。
訂閱：
文章 (Atom)