Equality in Sylvester's Inequality

Alright, back to the monthly posts. I have my final exams at the end of the month, after which I plan on studying more advanced Physics and College Maths. I'm already making progresses, as you may see after this post.

A while ago, one of my good friends showed me the problems he had to solve at the National phase of the Traian Lalescu contest. The first problem seemed rather interesting, and, as the title says, it involves an equality for the Sylvester inequality. As you may know, the Sylvester inequality states that, for two matrices \(A\) and \(B\) in \(M_n(C)\), \(rank(AB)≧ rank(A)+ rank(B)-n\). In this article, I will prove that, for any matrix \(A\) in \(M_n(C)\), \(n≧2\) and for any polynomial \(f\) of degree \(m≧1\) with the free coefficient \(a\) different from 0, we have that \(rank(f(A)*A)=rank(f(A))+rank(A)-n\).

Solution:

We know the fact that the rank of a matrix is the dimension of the image of the morphism associated with the matrix. By the dimension theorem, \((dim(Im (f(A)*A))+dim (Ker (f(A)*A))=n\), so \(dim(Ker (f(A)*A))=n-rank(f(A)*A))\), and, by using the dimension theorem for the other matrices and re-writing the equation in the conclusion, we need to prove that \(dim Ker(f(A)*A))=dim Ker (f(A))+dim Ker (A)\).

We shall now prove that \(Ker (f(A)*A)=KerA⊕Ker(f(A))\). First of all, let's prove that the direct sum between the two vector spaces exists. Let \(Z\) be an element of the Kernel of A different than 0. Thus, \(AZ=O\). Let m be the free coefficient of f. Thus, \(f(A)*Z=m*Z=O\) only if m is 0, which is false. Thus, no element of Ker(A) is in Ker(f(A)) other than the zero vector, so we can talk about a direct sum. We know that \(dim Ker A + dim Ker (f(A)) = dim (Ker A ⊕ Ker (f(A))\). Let us write \(W=Ker A⊕ Ker f(A)\).

We shall get back to proving that \(W=Ker(f(A)*A)\). Let \(Z=xX+yY\) be an element of W. We shall prove that it belongs to \(Ker(f(A)*A)\). \(f(A)*AZ=f(A)*A*(xX+yY)=f(A)*A*xX+A*f(A)*yY=O\), so we have proved that W is included in \(Ker(f(A)*A)\). Conversely, let \(Z\) be an element of \(Ker(f(A)*A)\). \(f(A)*A*Z=O\), so \(AZ\) belongs to Ker(f(A)). \(A*f(A)*Z=O\), so \(f(A)*Z\) belongs to \(Ker(A)\). Since \(AZ\) belongs to Ker(f(A)), \(f(A)*Z-aZ\) belongs to the Kernel, too.  Using the assertion that we've proven earlier, that W is included in \(Ker(f(A)*A)\), we get that \(f(A)Z-f(A)*Z+aZ\) is included in \(Ker(f(A)*A)\), so \(Z\) is included, too, because m is different than 0. Thus, \(Ker(f(A)*A)\) is included in W, and this implies that W is equal to \(Ker(f(A)*A)\). This concludes the proof.

The problem in the contest was a bit different, because the polynomial the jury chose was f(A)=mI-A. The generalized problem that I solved is much more interesting though. I always wondered how to reach the equality in Sylvester's inequality, and this problem sheds some light on that. However, this isn't my biggest curiosity in the realm of linear algebra. Back in the 11th grade, I was so scared of failing at the Olympiad, that I started dreaming problems at night. Here's one that I have no idea how to solve: what is the number of nilpotent matrices of order n with all entries being either 0 or 1? Of course, for n odd, there are no such matrices, but what happens for even n? I asked a friend to make a computer program, so we could compute the number. We did n=2 and n=4, but n=6 would have taken a few days to compute, so we gave up. If you know the solution to the problem I dreamt, make sure to send me a link in the comments! Tune in next time, for something completely random!

Cris.

Two matrix problems from recent Romanian Maths Olympiads

I normally don't do this kind of posts, but this year's ONM (this is the Romanian National Mathematics Olympiad; in Romanian, the adjectives and modifiers are placed after the noun) has been rather... awkward. The problems themselves were beautiful, I can't disagree, yet some were too easy for a National Olympiad, while some were too hard. The median score for the 12th grade was 3 points, and bronze medals were given to those with a score above 3.5, while silver medals were given to those with a score above 5 points. For comparison, at the 11th grade, silver medals were given to those with a score above 20 points.

This post can be regarded as a complaint to the Olympiad Committee. Last year, the subjects at the 11th grade were incredibly hard, while this year, they were incredibly easy. This difference between difficulty makes it harder for students to properly prepare for the Olympiad, and leads to anomalies in the hierarchies: hard subjects imply that students get points based on how much they guess (I put emphasis on the word 'guess') from the official solution, while easy subjects imply that many people solve them. As an example, I will discuss the solutions of the first problem from both Olympiads: the 2018 ONM and the 2019 ONM. I picked these problems because, usually, the first problems are the easiest during the contest. Even at the International Maths Olympiad, the first problem of each day is regarded as the easiest.

Problem one from ONM 2018: For every column vector X in \(M_{n,1}(Z)\), let \(c(X)\) be the least common divisor in the vector. Let A be a nxn matrix with integer entries. Prove that the following affirmations are equivalent:
1) \(|det(A)|\)=1.
2) \(c(AX)=c(X)\), for every vector X.

Solution:
1) implies 2) can be done by a double inequality. Obviously, c(AX) is bigger or equal to c(X), so we get that \(c(X)=c(A*A^{-1}X)≧c(AX)≧c(X)\), so \(c(AX)=c(X)\).
2) implies 1) is a bit harder. The official solution involves something regarding systems of equations, yet I solved it with a theorem regarding integer matrices. Any matrix A with integer entries can be written as A=U*J*V, where U and V are integer matrices with determinant of modulus 1, while J is a diagonal matrix with the integer elements \(d_1, d_2, ...d_n\) on the diagonal, in this order, such that \(d_1 | d_2 |... |d_n\).
By using this property, let us look at \(c(AX)=c(UJVX)\). By choosing \(X=V^{-1}X\), we get that \(c(UJVV^{-1}X)=c(UJX)=c(V^{-1}X)=c(X)\), because of the first implication. We shall now look at \(c(UJX)\) In order to prove that A has determinant plus or minus 1, we have to prove that J has only plus or minus 1 on its diagonal. Also, \(c(UJX)=c(JX)\), because JX is another vector. We shall look at \(c(JX)=c(X)\). Thus, for a vector \(X=(d_n, d_n, ... d_1)\), by doing JX, we get that \(d_1=d_n\). By taking an X such that \(c(X)=1\), we get that \(d_n=1\). Thus, the determinant of J has modulus 1, and A itself has modulus 1. This concludes the problem.

As you can see, the problem had a few intriguing ideas. The theorem made the whole problem easier, but it was still pretty hard. The official solution involved much more creativity. In total, about 5 people managed to solve this problem. I believe that this problem is good for the Olympiad, though it should be more of a problem 4 rather than one of many problems of same difficulty.

Let us get to the present day now...

Problem one from ONM 2019: Let A and B be complex nxn matrices such that there exists an idempotent matrix C with the property that C*=AB-BA. Prove that \((AB-BA)^2=O\).

Solution:
If C is idempotent, that means that its determinant is either 0 or 1. If its determinant is 1, then all its eigenvalues are 1, and, thus, the adjoint matrix has the same eigenvalues. With this in mind, the trace of C would be n, while the trace of AB-BA is 0, which is a contradiction. Thus, the determinant of C is 0. Let us use Sylvester's inequality on this: we have that \(rank(C^{*} C)≧ rank(C) + rank (C^{*}) - n\). With this in mind, \(n≧rank(C)+rank(C^{*})\). If \(rank(C)=n-1\), then rank (C*)=1, which implies that \(C^{*2}=Tr(C^{*})*C=O\) by writing C* in the specific form of a matrix with rank 1. If rank(C) is smaller or equal to n-2, then, by definition, C* is O, so \(AB-BA=O\). In both cases, \((AB-BA)^2=O\)

These properties of the adjoint matrix are well known in the Romanian Olympiad system. The problem is, in essence, hard, but most teachers show their students the properties of the adjoint matrix. I believe that this problem is a good opening problem, though, provided that the test increases in difficulty later on. This problem was solved by 52 students during the contest.

The point I'm really trying to make is that there must be a middle ground. An Olympiad's purpose should be to encourage children in following their passion, yet extremely hard or extremely easy problems might actually discourage them. Both problems become really easy if similar problems have been discussed before during class, yet the difference between them is that the first one involves a theorem that is not normally discussed in high school, while the second one only involves the 11th grade curriculum. A student may be able to solve the second problem even if he's never seen anything like it before, given enough creativity, but it would be impossible for him to re-discover the theorem used in the first problem. The official solution involves much more creativity than should be expected from one of the easier problems in the contest, and only a small fraction of the students, the best of the best, can come up with it. Yet the Olympiad isn't only about the top 5 students, but about all participants. During the 12th grade Olympiad this year, only 6 out of the 59 participants solved at least one problem, while the rest wrote down every idea they had with the hopes of it being in the official solution. Only one student solved more than two problems. I agree, the Olympiad shouldn't be easy, but it shouldn't be borderline impossible either.

This shouldn't be taken as an insult addressed to the Olympiad Committee. It's not. It's simply a complaint and a reason for the complaint. Besides, both problems are very beautiful, they truly represent high school Mathematics. But some problems, even though they are beautiful, just aren't meant for contests.

Alright folks, that's it for today. Tune in next time, for complex numbers, some algebra, or something completely random!

Cris.

Proof of the Riemann Hypothesis using a group with proper subgroups of order 2 and 3

1. Introduction

Back in 1859, German mathematician Bernhard Riemann introduced us to 6 important hypotheses...



Just kidding, did you really think I'd solve the Riemann Hypothesis here? April Fools joke!

Half of the title is correct, though. Today, we shall discuss a problem from the 2016 Maths Olympiad shortlist, proposed by Mihai Piticari. The problem goes as follows: Determine all finite groups which have proper subgroups only of order 2 or 3.

Solution:

First off, let us observe that the cardinal of the required group G is of the form \(2^i3^j\). By the Sylow theorem, we will have a subgroup of order \(2^i\) and a subgroup of order \(3^j\). If both of them are positive and one is bigger than 2, then we will have a subgroup larger than order 2 or 3. Thus, G can only have \(2^k\), \(3^k\) or 6 elements.

In the first case, we get that all elements have order 2, and, thus, \(xy=yx\), for all elements of G. If this happens, we have a subgroup of order 4, made of \(x, y ,xy ,e\), so the only groups working in this case are Klein's group and the group of order 2, C2.

In the second case, we shall use the equation of the classes. Let us observe that, if 2 elements that aren't part of the same subgroup commute, then we shall have a group of order 9. By the equation of the classes, we have that \(3^k=|Z(G)|+Σ\frac{|G|}{|C(G)}\), where the sum is made by a complete system of representatives with non-trivial orbit.. Since \(C(G)<4\) by the observation above, it is easy to see that \(C(G)=3\), and, thus, if k is bigger than 2, we will need the center of G to have a number of elements that is a multiple of 3. Thus, we get that the only possible groups are the group of order 3 and the group of order 9. Thus, G is C3 or C9 or C3xC3.

In the third case, we have that G is either C6 or C3xC3.

This problem might not have been as easy as the Riemann Hypothesis, but it was fun nonetheless. Seriously though, it would be fun if someone actually proposed a correct solution of the actual RH on the first of April and someone disregarded it as a prank. Jokes aside, tune in next time for some stuff about complex numbers, another algebra problem, another Millennium Prize problem, or something completely random!

Cris.