Isomorphic groups of integer matrices

My dudes, buckle up, because we're exploring the wonderful realm of abstract algebra again. I found the following problem in the latest number of the 'Gazeta Matematica' by a teacher called Dan Moldovan. I've got to say, the problem is amazing, and I thank this professor for proposing it.

Let \(m,n,p>2\) be natural numbers and let \(G=[A_1, A_2, ... A_p]\) matrices in \(M_{n}(Z)\). To every matrix in G, we attach the reduced matrix modulo m, \(\hat A_i\), so that, if \(A_i=(a_{i,j})\) is out matrix, then the reduced matrix is \(\hat A_i≡(\hat a_{i,j}\), where \(\hat a_{i,j}=a_{i,j}\)(modulo m). Prove that \(\hat G=[\hat A_1, \hat A_2,...\hat A_p]\), together with multiplication in \(M_n(Z)\), forms a group that's isomorphic with G.

Solution:

First of all, let us observe that the neutral element of G isn't \(I_n\). I know this sounds counter-intuitive, but take the group formed by an idempotent matrix with multiplication. The neutral element there is the matrix itself, so any idempotent matrix can be the neutral element of this group. For the sake of the problem, we shall consider the neutral element of G as \(I\). \(I\) has the property that \(I^2=I\), and \(AI=IA=A\) for any element \(A\) in G.

Let us consider the case in which \(I=O_n\). In this case, \(AO_n=A=O_n\), so G={\(O_n\)}, and \(\hat G=[\hat O_n]\), so the two groups are isomorphic.

If \(I\) is different from \(O_n\), then we shall prove that \(gcd(I)=1\). Let \(x=gcd(I)\), and it follows that \(I=xB\), where B is another matrix in \(M_n(Z)\). Since \(I^2=I\), \(x^2B^2=xB\), so \(xB^2=B\). Since \(B^2\) is different than 0 (because otherwise \(I=O_n\)), x divides all elements in B, so \(x^2\) divides all elements of I, which implies that \(x=1\).

I found the following lemma in the excellent article 'Finite Groups of Matrices Whose Entries Are Integers', published in AMC in 2002 by Mr. James Kuzmanovich and Mr. Andrey Pavlichenkov.(https://www.jstor.org/stable/2695329)

Lemma: Let G be a group of integer matrices in which there is an element \(A\) such that \(A^q=I\), with q prime, and \(\hat A=\hat I\), where \(\hat A\) is the reduced matrix modulo p, where p is another prime number. It follows that \(A=I\).

Proof: Since \(\hat A=\hat I\), \(A=I+pH_1\). Let \(gcd(H_1)=d\)
⟹\(A=I+pdH\), where \(gcd(H)=1\).
⟹\(A^q=(I+pdH)^q=I+\sum_{k=1}^q {{q}\choose{k}}(pd)^{k}H^k I^{q-k}=I\). However, \(I^n=I\), for all n, so \(\sum_{k=1}^q {{q}\choose {k}}(pd)^{k-1}H^k I=O_n\) (I divided by \(pd\). The only element without \(p\) in it is is \(qHI\), so p divides q, and, thus, p is q or p is 1. Since p is prime, p is q, and, by dividing the relation once more, we get that p divides \(gcdH\), so p is 1, which is a contradiction. Thus, \(H=O_n\), so \(A=I\).                           

Back to our problem, I shall prove something that probably everyone saw coming: the fact that \(f(X)=\hat X\) is the isomorphism we were looking for, where \(\hat A\) is the reduced matrix modulo m. Obviously, \(\hat I\) is the neutral element in \(\hat G\), and all the calculations are the same, so f is a morphism. Since \(G\) and \(\hat G\) are finite, we have to prove that the morphism is injective. For that, we shall prove that \(Ker (f)=[I]\).

Let us presume by absurd that there is an A in G such that \(f(A)=\hat A=\hat I\). Thus, \(A=I+mB\), so, because G has order p, \((I+mB)^p\). Let q be a prime factor of p. Thus, we have that
$$⟹((I+mB)^\frac{p}{q})^q=I$$
Since \(\frac {p}{q}=k\) is an integer, \((I+mB)^k=I+mH_1\), so \((I+mH_1)^q=I\).
$$⟹\sum_{j=1}^q {{q}\choose{k}}(mH_1)^j I=O_n$$
Let \(gcd H_1=d\), so \(H_1=dH\), with \(gcd(H)=1\). Thus,
$$\sum_{j=1}^q (md)^{j-1}H^j I= \sum_{j=1}^q (md)^{j-1} H^j =O_n$$
By using the same logic as before, \(md | qH\). Since \(gcd(H)=1\), m divides q, and, since m is bigger than 1, m is q. Because both m and q are prime, we can use the lemma, and, thus, H=0, so \((I+mB)^k=I\).

By applying this algorithm to all the prime divisors of k, we end up with \(mB=O_n\), so \(B=O_n\), so \(A=I\). Thus, Ker(f)={I}, so the morphism f is injective, and, consequently, bijective, so \(G\) and \(\hat G\) are isomorphic. This concludes the proof.

I can't really think of a paragraph ending this article, which is a total shame, since this problem was magnificent. I have an excuse though: I have the MAT in a few days, and I am a bit stressed out. I think I'll go play some World of Warcraft to relax. After the MAT, I will try posting more problems, though I came to realize the problems I post while under pressure are longer and harder than the normal problems I post. Maybe it's some kind of psychological mechanism behind this... I'm not foreshadowing the psychology article, btw.

Cris.

An application of Complex Algebra in Geometry

A few days ago, I wrote about posting my favorite problem. The thing about this problem is that it's extremely simple through synthetic geometry, but I found a way of solving it using complex numbers in a way that baffled me. It took 3 pages to solve this problem in my 'Notebook of Nice Problems' (which we shall call NNP from now on; I might even add a tag for problems I took from there). Some people have called me sadistic for liking this type of solutions, but I took it as a compliment. Without further ado, let's get right into the problem!

Let ABC be a triangle with AD as a bisector and AM as a median, with D and M laying on the line BC. Let P be a random point on AD, and E and F the projections of P on the lines AB and AC. If K is the intersection between EF and AM, prove that PK is perpendicular on BC.



First of all, we shall presume that ABC is not isosceles with AB=AC. If ABC is isosceles with AB=AC, then AD and AM coincide, and PK is obviously perpendicular on DC.

Let us use the transversal theorem in the triangle ABC. We shall consider the transversal E-K-F, and the line denoted by A-K-M, which passes through K. Thus, we get that $$BM \frac{FC}{FA} + MC \frac{EB}{EA} = BC \frac{KM}{KA}$$However, \(AM=MC=\frac{BC}{2}\), so we get that $$\frac{FC}{FA}+\frac{EB}{EA}=2\frac{KM}{KA}$$We shall call this relation (1). By using the property of points on the bisector, we get that \(PE=PF\), and, by triangle congruences, \(AE=AF\). Thus, (1) transforms into \( \frac{FC+EB}{2EA}=\frac{KM}{KA}\). However, \(FC=AC-AF\), and \(EB=AB-AE\), so the relation transforms further into \( \frac{AB+AC}{2EA} -1=\frac{KM}{KA}=r\).

Let us center the complex plane in A. By using the usual notations and by considering AB as the real positive axis, we have that \(e,b⋲R_{+}^*\). We can write \(k=\frac{m+r*a}{1+r}=\frac{m}{1+r}=\frac{b+c}{2(1+r)}\) (2)

Since \( PE⟘AB, PF⟘AC, PE=PF\), it follows that \(\frac{e-p}{b}⋲iR, \frac{f-p}{c}⋲iR, |e-p|=|f-p|\). $$\frac{e-p}{b}⋲iR ⟺ \frac{e-p}{b}=\frac{p^{*}-e^{*}}{b^{*}},$$where \(x^{*}\) is the conjugate of \(x\). $$⟹eb^{*}+e^{*}b=pb^{*}+p^{*}b$$
Similarly, we get that $$fc^{*}+f^{*}c=pc^{*}+p^{*}c$$We shall call these relations (3) and (4) respectively. Apologies for not being able to write the relations next to the equations, I still have to work on my Mathjax skills. I will (probably) learn how to fix this problem in the (far) future. If \(w=cosA+isinA ⟹ f=ew\). \(PK⟘BC ⟺\frac{k-p}{c-b}=\frac{p^{*}-k^{*}}{c^{*}-b^{*}}\).
$$⟺kc^{*}-pc^{*}-kb^{*}+pb^{*}=p^{*}c-ck^{*}-p^{*}b+bk^{*}$$
$$⟺kc^{*}+k^{*}c-bk^{*}-b^{*}k=p^{*}c+c^{*}p-p^{*}b-pb^{*}$$
$$⟺kc^{*}+k^{*}c-k^{*}b-kb^{*}=fc^{*}+f^{*}c-eb^{*}-e^{*}b$$The last line is obtained from combining (3) and (4), and we shall call it (5). Let us replace k as we obtained it in (2). Let us also remember that e and b are positive numbers, so they are equal to their conjugate and modulus.

$$⟹ (5) ⟺ \frac{(b+c)c^{*}}{2(1+r)}+\frac{(b^{*}+c^{*})c}{2(1+r)}-$$
$$-\frac{(b^{*}+c^{*})b}{2(1+r)}-\frac{(b+c)b^{*}}{2(1+r)}=ewc^{*}+ew^{*}c-eb^{*}-e^{*}b$$
$$⟺\frac{|c|^2-|b|^2|}{1+r}=ewc^{*}+ew^{*}c-eb-e^{*}b,$$which shall be known from now on as (6). Let us remember that \(\frac{AB+AC}{2EA}=1+r ⟹\frac{|b|+|c|}{2|e|}=1+r.\)
$$⟹ (6) ⟺ \frac{2e(|c|-|b|)(|c|+|b|)}{|b|+|c|}=ewc^{*}+ew^{*}c-eb-e^{*}b$$
$$⟺ 2(|c|-|b|)=cw^{*}+w^{*}c-2b$$
This shall be known as (7). However, \(c=\frac{w|c|b}{|b|}\).
$$⟹(7)⟺2(|c|-|b|)=ww^{*}b^{*}\frac{|c|}{|b|}+ww^{*}b\frac{|c|}{|b|}-2b$$
$$⟺2(|c|-|b|)=2b\frac{|c|-|b|}{|b|} ⟺ 2=2$$
The last line is true, because |c| is different than |b|, as AB is different than AC. Thus, \(PK⟘BC\) 𞺑

Writing that square at the end of this proof feels so satisfying. The calculations were very tedious when I first solved the problem, but I enjoyed it nonetheless. Of course, in the actual context of Mathematics, this proof isn't hard, but it's a nice exercise for anyone with basic knowledge of complex numbers and with a bit of imagination regarding Geometry.

P.S: This will be the last template update for a while, as I pretty much like this layout of the blog.

Cris.

Benford's Generalized Law

First of all, apologies for my lack of posts recently; school started for me, so I don't really have time for much. I have been working on an article regarding the Hollow Earth theory in which I debunked it, but, after writing the article, I realized that I made a mistake somewhere along the way, and, frankly speaking, I rage-quited. I still wanted to write an article, so I took out my 'notebook with notable problems' (I have one of those, I'm a full-time nerd), and I came across the Newcomb-Benford law, which states that the numerical values of the vast majority of social phenomena (the majority modeled by exponential evolutions in rapport to time) start with 1. The law takes its name from its two discoverers, Frank Benford, who wrote about it in 1938, and Simon Newcomb, who discovered it in 1881. Both discovered it independently from one another.  This problem was also proposed in a Gazeta Matematica back in February 2017.

Let \(f(t)=a^t\) be the function modeling a specific social event. We are looking at the values of t for which $$10^n<f(t)<2*10^n$$. By taking logarithms, we get that \( n<t log(a)<lg2 + n\). Thus, the probability that the first digit of f is 1 is log2, which is roughly equal to 0.301. For the general case, $$lg(d)+n<t lg(a)<lg(d+1)+n$$,where d is the first digit of f, so the probability that the first digit is d is equal to \(log(d+1)-log(d)\). The function \(log(x+1)-log(x)\) is decreasing for all positive x, so the probability of each digit appearing is decreasing. Obviously, the law works for all numerical bases.

We can also do a quick generalization of this result. How about we derive the n-th digit of an exponential function? Let us presume that the exponential function has m digits, with m bigger than n. Now, we know that \((10M+d)*10^{m+1-n}<a^t<(10M+d+1)*10^{m+1-n}\), where M is the number composed by the first n-1 digits. Thus, by taking logs again, we get that $$(m+1-n)log(10M+d)<tloga<(m+1-n)log(10M+d+1)$$, so the required probability, for a certain M, is \(log(1+ \frac {1}{10M+d})\). Since M is the number made by the first n-1 digits, it takes values from \( 10^{n-2}\) to \(10^{n-1}-1\), so the required probability is $$P(d)= \sum_{k=10^{n-2}}^{10^{n-1}-1} log(1+ \frac {1}{10k+d})$$.

After doing a quick search on Wikipedia, I found out that this result has some practical uses. Apparently, price digits and election results can be somehow checked by this law, and it appears to have applications in molecular genetics, too. Perhaps some old results like this are still revolutionary to this day.

Cris.

Old Topology Problem

'Gazeta Matematica', the most widely known Mathematical journal in Romania, begins its year by publishing problems from old years ending in the same digit as the year that just started. This year, they published problems from years ending in 8. The problem that I am about to share was published in 1968 by T. Zamfirescu, and is solvable through Helly's theorem. Without further ado, let's get straight into the problem.

Let d be a line in space and S a finite set of spheres such that any 3 spheres have an interior point in common. Prove that there exists a line d' parallel to d that intersects all the spheres.

Helly's theorem in a plane states that if a finite number of convex sets with the property that any three convex sets intersect, then all convex sets intersect.

Here's the proof of the theorem: Let m be smaller or equal to n, where m is the maximum number of sets with the intersection I different than the empty set and let us presume by absurd that \(m<n\), so there is C such that C doesn't intersect with I. Because C and I are convex sets, there must be a line d that separates them, they are in planes \(S_1\) and \(S_2\) respectively. Because \(m>2\), we need at least 3 sets to create I. Let \(C_1\) and \(C_2\) be two of them. Obviously, I is included in them. From the hypothesis, \(C_1\), \(C_2\) and C intersect. We choose the point A in their intersection and the point B in I. Thus, A is in \(S_1\) and B is in \(S_2\). Since A and B are in \(C_1\) and \(C_2\), the whole segment AB is in \(C_1\) and \(C_2\), and, thus, AB and d intersect. We now have that for any sets \(C_1\) and \(C_2\) that contain I, the intersection between \(C_1, C_2\) and d is not the empty set. By writing in a different form, we have that the intersection between \(C_1\) and d intersects with the intersection between $C_2$ and d. Thus, by considering the intersections as segments, we have m segments on a line such that each pair of segments intersects. By Helly's theorem on a line, we have that all the m segments intersect, so, by writing the intersection of the segments as the intersection of \(C_i\)-s and d, we have that I intersects with d, which is a contradiction. Thus, m=n.

Back to the problem at hand, let us consider a plane P such that d is perpendicular on P. Now, let us project the spheres on P. We get a set of circles with the property that any 3 of them intersect, and, thus, from Helly's theorem in a plane, we get that the circles intersect. Since the spheres intersect in an interior point, the circles have an actual surface in common, not only a point. Let A be a point in that surface. The line through A that is parallel to d is the required d'.

Of course, this problem isn't a hard topology problem, but it is pretty hard for the undergraduate level.

This article wasn't the different article that I promised. That one is still underway. Stay tuned folks, more problems/journals/randomness is coming.

Cris.

Matrix solvable through Jordan form

One of the worst experiences (and failures) of my life was the National Maths Olympiad from the 11th grade. It was a traumatizing experience, since the Olympiad took place in a remote part of the country (I come from Romania), and the subjects were incredibly hard. I managed to win a bronze medal, though I was very disappointed with myself. A month ago, I gathered my strength and looked through the shortlist for the Olympiad. The problem I am about to solve was the only linear algebra problem in the shortlist, and, just like the one from the Olympiad, it is solvable through the Jordan canonical form. The Jordan form wasn't part of the syllabus of the Olympiad, which was a dirty move from the problem selection committee. Nonetheless, I was inspired by this experience, and, in the meantime, I studied the canonical form.

Without further ado, let's get straight into the problem.

Let A be an \(n x n\) matrix with complex entries. Prove that \(A^2=O_{n}\) if and only if there are complex \(n x n\) matrices B and C such that \(A = BC\) and \(CB=O_{n}\).

I will post the matrices as photos, because posting them in Latex is tedious.

Let 1) be \(A^2=O_{n} => B, C\), and 2) be \(B, C => A^2=O_{n}\).

2) => 1)

$$A=BC, CB=O_{n}$$

$$A^2=B(CB)C=O_{n}$$

The next one will be 'slightly' longer.

1) => 2)

\(A^2=O_{n}\) Thus, the minimal polynomial of A divides \(X^2\).

1. The minimal polynomial of A is X, so \(A=O_{n}, B=O_{n}\), while C is any random matrix.

2. The minimal polynomial is \(X^2\)

We shall start using the Jordan canonical form. We know that the maximum order of any Jordan block corresponding to a specific eigenvalue is equal to the number of apparitions of \(X-a\) (where a is an eigenvalue) in the minimal polynomial. Thus, the maximum order of a Jordan cell is 2, and the Jordan canonical form of A looks something like this:

Everything above the J-s and 0-s is 0. The J-s look something like this:

We shall be looking for matrices B' and C' such that \(B' C' = J\) and \(C' B' = O_{n}\)

Let us write B' and C' in the form

   , .

We need to find \(B_{i}\) and \(C_{i}\) such that \(B_{i} C_{i} = J_{i}\) and $$C_{i} B_{i} = O_{n}$$. The perfect example of such matrices is \(B_{i}=J_{i}\) and \(C_{i}\) of the form

With \(B_{i}\) and \(C_{i}\) found, we can write B' and C'. 

Let S be a matrix such that \(SAS^{-1} = J\). Thus, \(S^{-1}JS=A\), and \(S^{-1}B' C' S=A\). We can take \(B=S^{-1}B'\), and \(C=C'S\). Thus, \(BC=A\) and \(CB=C'SS^{-1}B'=C'B'=O_{n}\), so there exist B and C, which concludes the problem.

It was very interesting to solve a problem with the Jordan canonical form, as the methods used aren't very common in high school Mathematics. The problem itself wasn't extremely difficult, yet it was interesting nonetheless. Tune in next time for an article that might be about something rather...different.

Cris.

                                                                                                                  

                                                                                                                  

Inequality involving Lagrange Multipliers

I'm not a big fan of inequalities, as I can't really solve one without having a book with theory in front of me. Who knows, maybe I'll make a post about interesting inequalities once.

Even though I'm not really a big fan of inequalities, I am a fan of analysis, and this was my introduction to multivariable calculus, so I enjoyed this problem. Of course, my approach may not be the simplest; when I asked one of my friends over at a beer about this problem, he said that he could have solved it using elementary inequalities. If you can find a solution using only elementary inequalities, I encourage you to write it down below. The problem was taken, yet again, from an AoPS post.

The problem goes something like this:

If  and  then prove that .


First off, we have to find an interval in which lie all the solutions of the given equations.
Thus, by using CBS,
$$(x+y+z+t)^{2}<4(x^2+y^2+z^2+t^2) $$, which implies that $$(-u)^2<4(20-u^2)$$.

\(u^2<80-4u^2,\) so \(5u^2<80\), and, thus, \(-4<u<4\). Obviously, all the other variables satisfy the same condition. Now we know that x,y,z,t,u are in [-4,4]. Let us now denote the following functions defined on \([-4,4]^5\) with values in the reals:

$$g_1(x,y,z,t,u) = x+y+z+t+u$$
$$g_2(x,y,z,t,u)=x^2+y^2+z^2+t^2+u^2-20$$
$$f(x,y,z,t,u)=x^4+y^4+z^4+t^4+u^4$$. 

We need to find the maximum value of the function $$F=f+ a g_1+ b g_2$$. Since \(f, g_1, g_2\) are derivable with a continuous derivative, the function F has a maximum on the given intervals, and, to find the maximum, we must differentiate F in x, y, z, t and u. In order to find the maximum, we must also use the fact that \(g_1=g_2=0\), which we know from the hypothesis. 

After differentiating, we get the following set of equations:

$$4x^3+a+2xb=0$$
$$4y^3+a+2yb=0$$
$$4z^3+a+2zb=0$$
$$4t^3+a+2tb=0$$
$$4u^3+a+2ub=0$$

Since the equation $$4x^3+2xb+c=0$$ has a maximum number of three solutions, we can discern between two cases: One in which there are two pairs of equal numbers among (x,y,z,t,u), and one in which there are 3 equal numbers.

FIRST CASE: x=y, z=t.

We now have that \(2x+2y+u=0\) and \(2x^2+2y^2+u^2=20\). By writing \(u=-2(x+y)\), we get that 

\(2x^2+2y^2+4(x+y)^2=20\), and, thus, \(6x^2+8xy+6y^2=20\), so \(3x^2+4xy+3y^2=10\) (1). 

By rising to the second power, we get that \((3x^2+4xy+3y^2)^2=100\), and, thus,

$$9x^4+24x^{3}y+34x^{2}y^{2}+24xy^{3}+9y^4=100$$, and, multiplying it by 2, we get that

$$18x^4+48x^{3}y+68x^{2}y^{2}+48xy^{3}+18y^4=200$$ 

Now, \(x^4+y^4+z^4+t^4+u^4=2x^4+2y^4+16(x^4+4x^{3}y+6x^{2}y^{2}+4xy^{3}+y^4 =\)
\(=18x^4+18y^4+64x^{3}y+64xy^{3}+96x^{2}y^{2}=\)
\(=200+16x^{3}y+16xy^{3}+28x^{2}y^{2}\), 

which is smaller or equal to 260 if and only if

$$16x^{3}y+16xy^{3}+28x^{2}y^{2}<60$$and, by dividing by 2,
$$8x^{3}y+8xy^{3}+14x^{2}y^{2}<30$$which can be written as
$$xy(8x^2+8y^2+14xy)<30$$ (*)

We know that \(|u|=|-2(x+y)|<4\), so \(|x+y|<2\). By squaring, we get that \((x+y)^2<4\), and \(x^2+y^2>2xy, so xy<1\) (2).

Since \((x+y)^2=x^2+y^2+2xy<4\),

\(2x^2+4xy+2y^2<8\), while \(3x^2+4xy+3y^2=10\) (from (1)). Thus, we get a new inequality:

\(x^2+y^2>2\) (3)

Now, we write $$14xy=(28xy)/2=[70-21(x^2+y^2)]/2$$. Back to (*), we get that

$$xy(8x^2+8y^2+14xy)<xy[8x^2+8y^2+35-(21/2)(x^2+y^2)]=$$
$$(xy/2)[70+16(x^2+y^2)-21(x^2+y^2)]= (xy/2)[(70-5(x^2+y^2)]$$, which is, according to (3), smaller than $$(xy/2)(70-10)<30xy<30$$, so (*) is proven.

If you have come this far, I suppose you are curious about the second case, too. Writing this is kind of tedious, but fun nonetheless.

SECOND CASE: x=y=z

\(3x+u+t=0\), \(3x^2+u^2+t^2=20\), so \(u+t=-3x\) and \(u^2+t^2+2ut=9x^2\).
We also know that \(u^2+t^2=20-3x^2\), so \(ut=6x^2-10\)

Thus, \(t^4+u^4=(t^2+u^2)^2-2(tu)^2=\)
\(=400-120x^2+9x^4-2(36x^4-120x^2+100)=200+120x^2-63x^4\).

$$x^4+y^4+z^4+t^4+u^4=-60x^4+120x^2+200$$.

We have to find the maximum value of this expression on the interval [-4,4]. Let us write \(A=x^2\). Now, the function we have to evaluate is \(g(A)=-60A^2+120A+200\), which obviously has a maximum value, because it's a grade two function and the coefficient of the greatest power is negative.

By differentiating, we have to find the A for which $$g'(A)=-120A+120=0$$ only when \(A=1\), and, thus, the maximum value of \(x^4+y^4+z^4+t^4+u^4=260\).

Thus, after solving both cases, we can conclude that \(x^4+y^4+z^4+t^4+u^4<260\).

Note that, wherever I wrote <, I meant smaller or equal to something. I am still working on my Latex skills, and, for me, writing the full proof of this inequality was a feat of strength.

I have found another inequality that seems solvable with Lagrange Multipliers a while ago, yet I haven't solved it yet. If I manage to solve it, I'll make sure to post it. If you people have a solution to this problem that doesn't involve Lagrange Multipliers, please write it in the comments. I'm really curious about it :)

Cris.