28/Jan/2015 IMC SEMINAR Linear Algebra II Warm-up 1. (IMC 2001) Let n be a positive integer. Consider an n × n matrix with entries 1, 2, ..., n2 written in order starting top left and moving along each row in turn left-to-right. We choose n entries of the matrix such that exactly one entry is chosen in each row and each column. What are the possible values of the sum of the selected entries? Solution. Since there are exactly n rows and n columns, the choice is of the form {(j, σ(j))|j = 1, ..., n} where σ ∈ Sn is a permutation. Thus the corresponding sum is equal to n X n(j − 1) + σ(j) = j=1 n X nj − n X j=1 = That is, there is only one possible sum. j=1 n+ n X σ(j) j=1 n(n2 + 1) . 2 2. (IMC 2011) Does there exist a real 3 × 3 matrix A such that tr(A) = 0 and A2 + AT = I? (tr(A) denotes the trace of A, AT is the transpose and I is the identity matrix.) Solution. The answer is NO. The idea is to find a polynomial p such that p(A) = 0 and then argue by contradiction using the possible eigenvalues. Take the transpose of A2 + AT = I, obtaining (AT )2 + A = I then substitute the value of the transpose from the first equation, hence I − 2A2 + A4 + A = I We know that the eigenvalues of A√have to be roots of the polynomial x4 − 2x2 + x = x(x − 1)(x2 + x − 1), namely 0, 1, 1±2 5 . √ Also, the eigenvalues of A2 are the squares of the eigenvalues of A, so these can be 0, 1, 3∓2 5 . Finally, we use the trace condition, tr(A) = 0 = the sum of its eigenvalues, the only possibility for this is (0, 0, 0). And by tr(A2 ) = tr(I − AT ) = 3 = sum of the squares of the eigenvalues of A, which is incompatible with the previous. Hence there is no such a matrix A. 3. Suppose that you have 2015 coins with integer numbers on them, such that given any coin, the other 2014 can be split into two groups of 1007 each, such that the sum of numbers of one group is same as the sum of numbers as the other. Show that all the coins have the same numbers. Solution. Construct the vector v = (x1 , ..., x2015 ) and let A be the matrix with 0’s on the diagonal and ±1 off the main diagonal that takes into account the splitting into two groups, that is, such that Av = 0. 1 First we will prove that there cannot be integer solutions other than the trivial (a, ..., a). Indeed, suppose there is a non-trivial integer solution v ∈ Ker(A) ∩ Z2015 , by the integer assumption we can suppose that v is mininal, i.e., that kvk is as small as possible. Now, if all the entries of v are even, then we get a contradiction to minimality because 21 v is also a non-trivial integer solution. If one of the entries is odd we will prove that all of them are odd. Indeed, consider S = x1 +...+x2015 . The condition of the problem implies that S−xi is even for all i, in particular for the one we are assuming is odd, hence S is odd as well. Therefore xi = S −Si must be odd for → − all i. This is also a contradiction to minimality since 21 (v − 1 ) is a non-trivial solution which → − → − → − is closer to the origin than v (Here 1 = (1, ..., 1) and k 12 (v − 1 )k < 12 (kvk + k 1 k) ≤ kvk, → − the latter because the entries of v are odd integers so kvk ≥ k 1 k). This finishes the part when the entries of v are integers. Homework. Bring your solutions next session on February 4th. 1. Suppose that you have 2015 coins with real numbers on them, such that given any coin, the other 2014 can be split into two groups of 1007 each, such that the sum of numbers of one group is same as the sum of numbers as the other. Show that all the coins have the same numbers. 2. Let A be a real 4 × 2 matrix and B be a real 2 × 4 matrix such that   1 0 −1 0  0 1 0 −1  . AB =   −1 0 1 0  0 −1 0 1 Find BA. 3. Let n be a fixed positive integer. Determine the smallest possible rank of an n×n matrix that has zeros along the main diagonal and strictly positive real numbers off the main diagonal. P 1 n 4. For an m × m real matrix A, eA is defined as ∞ n=0 n! A (the sum is convergent for all matrices). Prove that for all real polynomials p and m × m real matrices A and B, the characteristic polynomials of p(eAB ) and p(eBA ) are the same. 2