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.

Something similar to Fermat's Last Theorem on non-field finite rings

Finally, another post!

Today I shall discuss a problem from the National Maths Olympiad from 2000, the year I was born. Judging by the usual schedule of the Olympiad, this problem is probably my twin. It caught my eye because it literally disproves Fermat's Last Theorem on finite rings that are not fields (the title already said that). The FLT is, of course, a much harder problem than what I'm about to solve in the next few lines, but that doesn't make this problem less important.

Let (A,+,*) be a finite ring with 1 different from 0. Prove that the following affirmations are equivalent:
1. A is not a field.
2. The equation \(x^n+y^n=z^n\) has a solution for every natural n.

Solution:

We shall first prove that 2 implies 1. Let us presume by absurd that A is a field. Thus, since A is a field, (A\{0},*) is a finite group, with an order equal to a certain \(t\). For that \(t\), \(x^t=1\), for all elements of A\{0}. Thus, since the equation \(x^t+y^t=z^t\) has a solution, \(1+1=1\), so \(1=0\), which is false. Thus, A is not a field.

Conversely, if A is not a field, it means that it has a non-invertible element, let's call it \(x\). Since A is a finite ring, there are \(i<j\) such that \(x^i=x^j\), and, thus, \(x^i (x^{j-i}-1)=0\). By writing \(t=x^{i-1}(x^{j-1}-1)\), we have that \(x*t=t*x=0\). Now, let us take \((x+t)^n\). By the binomial theorem, this is a sum of combinations which revolve around \(x\) and \(t\), and, because \(x*t=t*x=0\), \((x+t)^n=x^n+t^n\), for all n, and, thus, we have a solution of the equation for every n.

Don't you think that this problem is really cute? I mean, it came 5 years after the proof of the FLT, and I am certain that the guy who proposed the problem had this in mind. I hope that my proof is correct, judging by the fact that the FLT has the unique record of having received the greatest amount of wrong solutions. Apparently, the peeps at the Wolfskehl committee received about 3 meters (in height) of wrong proofs. That might not sound like much, but when you think about the amount of pages required, you'll figure out that it's a really big lot. Tune in next time for trigonometric functions defined on complex numbers, another abstract algebra problem, or something completely random!

Cris.