Intermediate Math Challenge - September 2018

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #1
15,415
13,436
Summer is coming and brings a new basic math challenge! Enjoy! For more advanced problems you can check our other basic level math challenge thread!

RULES:

a) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
b) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
c) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
d) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
e) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems. In case of an inadvertent posting of a solution the post will be deleted.

We have quite a couple of old problems, which are still open. As we think that most of them aren't too difficult, we want to give them another try. One reason is, we want to find out why they have been untouched. So in case you need a hint or two in order to tackle them, don't hesitate to ask! We've also some new questions. Our special thanks go to @Infrared who contributed some new questions.

QUESTIONS:

1. (solved by @Citan Uzuki )
  • Prove for any ##\mathbf X \in \mathbb R^{\text{ n x n }}## there exists some ##\mathbf Z## such that ##\mathbf {XZX} = \mathbf X##
  • Prove that a satisfying ##\mathbf Z## may be chosen to obey
    ##\text{trace}\big(\mathbf {ZX}\big) = \text{rank}\big(\mathbf X\big)##
    ##\text{trace}\big(\mathbf {ZX}^3\big) = \text{trace}\big(\mathbf {X}^2\big)##
2. We consider the vector field ##X\, : \,\mathbb{R}\longrightarrow \mathbb{R}^2## given by ##X(p) := \left(p,\begin{pmatrix} 1\\0 \end{pmatrix}\right)\,.##
  • Compute the derivative ##d\phi\, : \,T\mathbb{R}^2\longrightarrow T\mathbb{R}^3## of the stereographic projection to the north pole, i.e. plane to sphere with ##\phi(0,0)=(0,0,-1)##, and describe the tangent bundle ##T\mathbb{S}^2## of ##\mathbb{S}^2##. Show that position vectors and tangent vectors are orthogonal.
  • Compute the vector field ##d\phi(X)## on ##\mathbb{S}^2##. How is it related to the curves ##\gamma(t)=\phi(t,y_0)\,?##
  • Is ##d\phi(X)## a continuous vector field on ##\mathbb{S}^2## without zeros?
Hint: The stereographic projection to the north pole is given by
\begin{align*}
\phi\, &: \, \mathbb{R}^2\longrightarrow \mathbb{R}^3\\
\phi(x,y)&=\dfrac{1}{x^2+y^2+1} \begin{bmatrix}
2x\\2y\\x^2+y^2-1
\end{bmatrix}
\end{align*}

3. A covering space ##\tilde{X} ## of ##X## is a topological space together with a continuous surjective map ##p\, : \,\tilde{X} \longrightarrow X\,,## such that for every ##x \in X## there is an open neighborhood ##U\subseteq X## of ##x,## such that ##p^{-1}(U)\subseteq \tilde{X}## is a union of pairwise disjoint open sets ##V_\iota## each of which is homeomorphically mapped onto ##U## by ##p##. A Deck transformation with respect to ##p## is a homeomorphism ##h\, : \,\tilde{X} \longrightarrow \tilde{X}## with ##p \circ h=p\,.## Let ##\mathcal{D}(p)## be the set of all Deck transformations with respect to ##p##.
  • Show that ##\mathcal{D}(p) ## is a group.
  • If ##\tilde{X}## is a connected Hausdorff space and ##h \in \mathcal{D}(p)## with ##h(\tilde{x})=\tilde{x}## for some point ##\tilde{x}\in \tilde{X}\,.## then ##h=\operatorname{id}_{\tilde{X}}\,.##
Hint: Show that ##\mathcal{D}(p)## is closed under inversion and multiplication. Then consider ##A:=\{\,\tilde{x}\in \tilde{X}\, : \,h(\tilde{x})=\tilde{x}\,\}\,.##

4. Given the Heisenberg algebra $$\mathcal{H}=\left\{\,\begin{bmatrix} 0&x&z\\0&0&y\\0&0&0 \end{bmatrix}\,\right\}=\langle X,Y,Z\,:\,[X,Y]=Z \rangle $$ and $$\mathfrak{A(\mathcal{H})}=\{\,\alpha\, : \,\mathcal{H}\longrightarrow \mathcal{H}\, : \,[\alpha(X),Y]=[\alpha(Y),X]\,\forall\,X,Y\in \mathcal{H}\,\} $$
Since ##\mathfrak{A(\mathcal{H})}## is a Lie algebra and $$[X,\alpha]=[\operatorname{ad}(X),\alpha]=\alpha(X)\circ \alpha - \alpha \circ \operatorname{ad(X)}$$ a Lie multiplication, we can define
\begin{align*}
\mathcal{H}_0 &:= \mathcal{H}\\
\mathcal{H}_{n+1} &:= \mathcal{H}_n \ltimes \mathfrak{A(\mathcal{H}_n)}
\end{align*}
and get a series of subalgebras $$\mathcal{H}_0 \leq \mathcal{H}_1 \leq \mathcal{H}_2 \leq \ldots$$
Show that
  • ##\mathfrak{sl}(2)<\mathcal{H}_n## is a proper subalgebra for all ##n\ge 1##
  • ##\dim \mathcal{H}_{n} \ge 3 \cdot (2^{n+1}-1)## for all ##n\ge 0##, i.e. the series is infinite and doesn't get stationaryl
As a counterexample, if we started with ##\mathcal{H}=\mathfrak{su}(2)\text{ or }\mathfrak{su}(3)## we would get ##\mathcal{H}_n=\mathcal{H}_0## and we were stationary right from the start, which can easily be seen by solving the corresponding system of linear equations.

Hint: The multiplication in ##\mathcal{H}_n## is given by $$
[(X,\alpha),(Y,\beta)]=([X,Y],[\alpha,\beta]+[\operatorname{ad}(X),\beta]-[\operatorname{ad}(Y),\alpha])$$ However, it is not really needed here. Calculate ##\mathfrak{A}(\mathcal{H})=\mathfrak{A}(\mathcal{H}_0)## and find a copy of ##\mathfrak{sl}(2)## in it, i.e. a ##2 \times 2## block with zero trace. Then note that all ##\mathcal{H}_n## have a central element (= commutes with all others), and consider its implication for ##\mathfrak{A}(\mathcal{H}_n)\,.## Proceed by induction.

5. On the occasion of the centenary of Emmy Noether's theorem.
This example requires some introduction for all members who aren't familiar with the matter, so let me first give some background information.
The action on a classical particle is the integral of an orbit ##\gamma\, : \,t \rightarrow \gamma(t)## $$ S(\gamma)=S(x(t))= \int \mathcal{L}(t,x,\dot{x})\,dt $$ over the Lagrange function ##\mathcal{L}##, which describes the system considered. Now we consider smooth coordinate transformations
\begin{align*}
x &\longmapsto x^* := x +\varepsilon \psi(t,x,\dot{x})+O(\varepsilon^2)\\
t &\longmapsto t^* := t +\varepsilon \varphi(t,x,\dot{x})+O(\varepsilon^2)
\end{align*}
and we compare $$ S=S(x(t))=\int \mathcal{L}(t,x,\dot{x})\,dt\text{ and }S^*=S(x^*(t^*))=\int \mathcal{L}(t^*,x^*,\dot{x}^*)\,dt^* $$
Since the functional ##S## determines the law of motion of the particle, $$S=S^*$$ means, that the action on this particle is unchanged, i.e. invariant under these transformations, and especially
\begin{equation*}
\dfrac{\partial S}{\partial \varepsilon}=0 \quad\text{ resp. }\quad \left. \dfrac{d}{d\varepsilon}\right|_{\varepsilon =0}\left(\mathcal{L}\left(t^*,x^*,\dot{x}^*\right)\cdot \dfrac{dt^*}{dt} \right) = 0 ~~(*)
\end{equation*}
Emmy Noether showed exactly hundred years ago, that under these circumstances (invariance), there is a conserved quantity ##Q##. ##Q## is called the Noether charge. $$S=S^* \Longrightarrow \left. \dfrac{d}{d\varepsilon}\right|_{\varepsilon =0}\left(\mathcal{L}\left(t^*,x^*,\dot{x}^*\right)\cdot \dfrac{dt^*}{dt} \right) = 0 \Longrightarrow \dfrac{d}{dt}Q(t,x,\dot{x})=0$$
with $$Q=Q(t,x,\dot{x}):= \sum_{i=1}^N \dfrac{\partial \mathcal{L}}{\partial \dot{x}_i}\,\psi_i + \left(\mathcal{L}-\sum_{i=1}^N \dfrac{\partial \mathcal{L}}{\partial \dot{x}_i}\,\dot{x}_i\right)\varphi = \text{ constant}$$
The general way to proceed is:
A. Determine the functions ##\psi,\varphi##, i.e. the transformations, which are considered.
B. Check the symmetry by equation (*).
C. If the symmetry condition holds, then compute the conservation quantity ##Q## with ##\mathcal{L},\psi,\varphi\,.##
Example: Given a particle of mass ##m## in the potential ##U(\vec{r})=\dfrac{U_0}{\vec{r\,}^{2}}## with a constant ##U_0##. At time ##t=0## the particle is at ##\vec{r}_0## with velocity ##\dot{\vec{r}}_0\,.##

Hint: The Lagrange function with ##\vec{r}=(x,y,z,t)=(x_1,x_2,x_3,t)## of this problem is $$ \mathcal{L}=T-U=\dfrac{m}{2}\,\dot{\vec{r}}\,^2-\dfrac{U_0}{\vec{r\,}^{2}} $$
a) Give a reason why the energy of the particle is conserved, and what is its energy?
b) Consider the following transformations with infinitesimal ##\varepsilon##
$$\vec{r} \longmapsto \vec{r}\,^*=(1+\varepsilon)\,\vec{r}\,\, , \,\,t\longmapsto t^*=(1+\varepsilon)^2\,t$$
and verify the condition (*) to E. Noether's theorem.
c) Compute the corresponding Noether charge ##Q## and evaluate ##Q## for ##t=0##.
Use ##\psi_i=0 , \varphi=1## for the time invariant energy and consider $$\left. \dfrac{d}{d\varepsilon}\right|_{\varepsilon =0}\left(\mathcal{L}\left(t^*,x^*,\dot{x}^*\right)\cdot \dfrac{dt^*}{dt} \right)$$ For the last part we have ##\partial_x \psi=x\; , \;\partial_y \psi=y\; , \;\partial_z \psi=z## and ##\varphi =2t\,.##

6. Consider the Lie algebra of skew-Hermitian ##2\times 2## matrices ##\mathfrak{g}:=\mathfrak{su}(2,\mathbb{C})## and the Pauli matrices (note that Pauli matrices are not a basis!)
$$
\sigma_1=\begin{bmatrix}0&1\\1&0\end{bmatrix}\, , \,\sigma_2=\begin{bmatrix}0&-i\\i&0\end{bmatrix}\, , \,\sigma_3=\begin{bmatrix}1&0\\0&-1\end{bmatrix}
$$
Now we define an operation on ##V:=\mathbb{C}_2[x,y]##, the vector space of all complex polynomials of degree less than three in the variables ##x,y## by
\begin{align*}
\varphi(\alpha_1\sigma_1 +\alpha_2\sigma_2+\alpha_3\sigma_3)&.(a_0+a_1x+a_2x^2+a_3y+a_4y^2+a_5xy)= \\
&= x(-i \alpha_1 a_3 +\alpha_2 a_3 - \alpha_3 a_1 )+\\
&+ x^2(2i\alpha_1 a_5 +2 \alpha_2 a_5 + 2\alpha_3 a_2 )+\\
&+ y(-i\alpha_1 a_1 -\alpha_2 a_1 +\alpha_3 a_3 )+\\
&+ y^2(2i\alpha_1 a_5 -2\alpha_2 a_5 -2\alpha_3 a_4 )+\\
&+ xy(-i\alpha_1 a_2 -i\alpha_1 a_4 +\alpha_2 a_2 -\alpha_2 a_4 )
\end{align*}
Show that
  • an adjusted ##\varphi## defines a representation of ##\mathfrak{su}(2,\mathbb{C})## on ##\mathbb{C}_2[x,y]##
  • Determine its irreducible components.
  • Compute a vector of maximal weight for each of the components.
Hint: This is an easy example of a ##\mathfrak{su}(2,\mathbb{C})## representation which shall demonstrate how the ladder up and down operators actually work. Choose ##(1,x,y,x^2,xy,y^2)## as ordered basis for the representation space ##V=\mathbb{C}_2[x,y]## and verify ##[\varphi(\alpha_1,\alpha_2,\alpha_3),\varphi(\alpha'_1,\alpha'_2,\alpha'_3)]=\varphi([(\alpha_1,\alpha_2,\alpha_3),(\alpha'_1,\alpha'_2,\alpha'_3)])## with the adjusted transformation
$$
\varphi(\alpha_1,\alpha_2,\alpha_3):=\varphi(\alpha_1\cdot (i\sigma_1),\alpha_2\cdot (i\sigma_2),\alpha_3\cdot (i\sigma_3))
$$
and decompose ##V## into three invariant subspaces. To determine the weights, consider the ##\mathbb{C}-##basis $$H=\sigma_3,X=\dfrac{1}{2}\sigma_1+\dfrac{1}{2}i\sigma_2,Y=\dfrac{1}{2}\sigma_1-\dfrac{1}{2}i\sigma_2$$

7. Let ##f\, : \,(0,1)\longrightarrow \mathbb{R}## be Lebesgue integrable and $$
Y := \{\,(x_1,x_2)\in\mathbb{R}^2\,|\,x_1,x_2\geq 0\, , \,x_1+x_2\leq 1\,\}
$$
Show that for any ##\alpha_1\, , \,\alpha_2 > 0##
$$
\int_Y f(x_1+x_2)x_1^{\alpha_1}x_2^{\alpha_2}\,d\lambda(x_1,x_2) = \left[\int_0^1 f(u)u^{\alpha_1+\alpha_2+1}\,d\lambda(u) \right]\cdot \left[\int_0^1 v^{\alpha_1}(1-v)^{\alpha_2}\,d\lambda(v) \right]
$$
Hint: Consider ##\phi\, : \,(0,1)^2\longrightarrow \mathbb{R}^2## with ##\phi(u,v)=(vu,(1-v)u)\,.## and apply Fubini's theorem.

8. A function ##|\,.\,|\, : \,\mathbb{F}\longrightarrow \mathbb{R}_{\geq 0}## on a field ##\mathbb{F}## is called a value function if
\begin{align*}
&|x|=0 \Longleftrightarrow x=0 \\
&|xy| = |x|\;|y|\\
&|x+y| \leq |x|+|y|
\end{align*}
It is called Archimedean, if for any two elements ##a,b\,\,(a\neq 0)## there is a natural number ##n## such that ##|na|>|b|\,.## We consider the rational numbers. The usual absolute value
$$
|x| = \begin{cases} x &\text{ if }x\geq 0 \\ -x &\text{ if }x<0\end{cases}
$$
is Archimedean, whereas the trivial value
$$
|x|_0 = \begin{cases} 0 &\text{ if }x = 0 \\ 1 &\text{ if }x\neq 0\end{cases}
$$
is not.
Determine all non-trivial and non-Archimedean value functions on ##\mathbb{Q}\,.##

Hint: This is indeed a bit tricky. Since ##|\,.\,|## is non-Archimedean, there are elements ##a,b## with ##|n|<\frac{|b|}{|a|}## for all ##n\in \mathbb{N}\,.## If ##|n| > 1## for a natural number, then ##|n^k|=|n|^k## goes to infinity and cannot be bounded. Thus ##|n|\leq 1## for all ##n\in \mathbb{N}\,.## Note that ##|.|## is non-trivial. Pick a smallest natural number ##n_0=ab## and investigate it.

9. (solved by @lpetrich ) Let ##G## be a group of order ##p^n## for some natural number ##n>1##. Show that ##\text{Aut}(G)## contains an element of order ##p##.

10. (solved by @nuuskur ) Let ##(X,d)## be a metric space. For open sets ##U\subset X##, let ##*U## denote the interior of the complement of ##U##. Give an example where ##**U\neq U##. Show that ##***U=*U## always holds.
 
Last edited:
  • Like
Likes Greg Bernhardt and member 587159

Answers and Replies

  • #2
986
174
I will do a partial solution of Question 9.
Our first task is to look for ways of simplifying the problem, and a rather simple way is to consider kinds of automorphisms. The main kinds are inner and outer automorphisms. Inner automorphisms are induced by conjugating every element of a group by some element, and outer automorphisms, all the rest. Here is conjugation of element x by element a: ##x^a = a x a^{-1}##.

At first sight, one might conclude that the inner-automorphism group Inn(G) of group G is G itself. But for all elements of Z(G), the center of of G, one gets the trivial automorphism, and one finds that each coset of Z(G) in G generates a separate automorphism. Furthermore, left and right cosets are identical, since every element of Z(G) commutes with every element of G. Thus, Z(G) is a normal subgroup of G, and Inn(G) is the quotient group G/Z(G).

Having split up the automorphisms, I turn to splitting up the group. A simple split is abelian vs. nonabelian. For G being abelian, G = Z(G), Inn(G) is the identity group, and all G's nontrivial automorphisms are outer ones. But for G being nonabelian, G is a proper superset of Z(G), and thus, Inn(G) is nontrivial. So I next consider the cases of G being abelian and G being nonabelian.

I first consider the case of G being nonabelian.

In that case, Inn(G) is nontrivial. I will seek order-p elements of that group in the following manner: (1) find the possible order values of Inn(G), (2) find the possible order values of its elements, and (3) find some order-p elements.

(1) From Lagrange's theorem, for G having order pn, the order of Z(G) is pm, where m must be at most n. From conjugacy-class sizes, m must be at least 1. Since Inn(G) = G/Z(G), the order of Inn(G) is therefore pn-m.

(2) Since the order of Inn(G) is a power of p, the orders of its elements must also be powers of p, and the orders of its non-identity elements must be nonzero powers of p.

(3) For an element with order pk, if k = 1, our task is done -- the element has order p. But if the element's order has k > 1, then one can construct power pk-1 of that element, and this new element has order p.

Thus showing that for G nonabelian, Inn(G) has some elements with order p, and thus the full automorphism group, Aut(G) does also.

I will consider the case of G being abelian in my next post.
 
  • #3
986
174
I will continue with the solution of Question 9.
In my previous post, I considered the case of G being nonabelian. I here consider the case of G being abelian. In this case, all but the identity element of the automorphism group are outer automorphisms.

I first look for a way of breaking down G to make the problem simpler. There is one -- breakdown into a direct product of cyclic subgroups: ##G = G_1 \times G_2 \times \cdots \times G_c##. By Lagrange's theorem, each of these subgroups has an order that is some nonzero power of p, and all those powers add up to make n.

The automorphisms of G thus include combinations of automorphisms of all these cyclic-subgroup parts. Since each such subgroup has one generator, its automorphism thus maps one of its generators onto a power of it that is relatively prime with the group's order. A combination-automorphism element of Aut(G) thus includes all of these powers.

Since we seek an element of Aut(G) with order p, we consider the possible orders of the combination automorphisms. The order of such an automorphism is the least common multiple of the orders of its automorphisms of all of the cyclic-subgroup parts. That is because each such automorphism's order must evenly divide the combination-automorphism order. So if a combination automorphism has order p, then each of the cyclic-part automorphisms must have order 1 or p.

This reduces the problem from finding an order-p automomorphism of an abelian group with power-of-p order to doing that for a cyclic group.

The automorphisms of a cyclic group map a generator onto all of the other generators. That is, for generator a, ##a \to a^b## for power b relatively prime to the order of the group. That means that the order of the automorphism group is the Euler totient function of the order of the group. In this case, ##\phi(p^n) = p^{n-1} (p -1)##. We then use Cauchy's theorem, which states that for every prime factor of the order of a group, that group contains at least one element with that prime factor as its order. For n > 1, the automorphism-group order is divisible by p, therefore the automorphism group has an element of order p. That is not the case for n = 1.

Thus, the automorphism group of cyclic group Z(pn) for n > 1 contains an element with order p, the kind of automorphism element that we were seeking. From my discussion of combination automorphisms, this means that if G contains such a cyclic group, that subgroup can have an order-p automorphism-group element and all the others can have the identity automorphism, giving that combination automorphism order p, what we were seeking.

This leaves the case of powers of Z(p), a group whose automorphism group has an order not divisible by p. I will consider that case in my next post.
 
  • #4
15,415
13,436
I will do a partial solution of Question 9.
Our first task is to look for ways of simplifying the problem, and a rather simple way is to consider kinds of automorphisms. The main kinds are inner and outer automorphisms. Inner automorphisms are induced by conjugating every element of a group by some element, and outer automorphisms, all the rest. Here is conjugation of element x by element a: ##x^a = a x a^{-1}##.

At first sight, one might conclude that the inner-automorphism group Inn(G) of group G is G itself. But for all elements of Z(G), the center of of G, one gets the trivial automorphism, and one finds that each coset of Z(G) in G generates a separate automorphism. Furthermore, left and right cosets are identical, since every element of Z(G) commutes with every element of G. Thus, Z(G) is a normal subgroup of G, and Inn(G) is the quotient group G/Z(G).

Having split up the automorphisms, I turn to splitting up the group. A simple split is abelian vs. nonabelian. For G being abelian, G = Z(G), Inn(G) is the identity group, and all G's nontrivial automorphisms are outer ones. But for G being nonabelian, G is a proper superset of Z(G), and thus, Inn(G) is nontrivial. So I next consider the cases of G being abelian and G being nonabelian.
I first consider the case of G being nonabelian.

In that case, Inn(G) is nontrivial. I will seek order-p elements of that group in the following manner: (1) find the possible order values of Inn(G), (2) find the possible order values of its elements, and (3) find some order-p elements.

(1) From Lagrange's theorem, for G having order pn, the order of Z(G) is pm, where m must be at most n. From conjugacy-class sizes, m must be at least 1. Since Inn(G) = G/Z(G), the order of Inn(G) is therefore pn-m.
Why can't we have a group ##G## with ##Z(G)=\{\,1\,\}\,##? And most of all: Where did you need this?
(2) Since the order of Inn(G) is a power of p, the orders of its elements must also be powers of p, and the orders of its non-identity elements must be nonzero powers of p.

(3) For an element ...
##g \in G##
... with order pk, if k = 1, our task is done -- the element has order p ...
and thus ##x \longmapsto x^g=gxg^{-1}## is also of order ##p\,.##
. But if the element's order has k > 1, then one can construct power pk-1 of that element,...
namely ##g^{(p^{k-1})}##
... and this new element has order p.

Thus showing that for G nonabelian, Inn(G) has some elements with order p, and thus the full automorphism group, Aut(G) does also.

I will consider the case of G being abelian in my next post.
To summarize your proof so far:

Case 1: ##G## is not Abelian. Then there is an element ##g \in G## for which ##x \longmapsto \sigma(g)(x)=x^g=gxg^{-1}## is not the identity, for otherwise ##G## would be Abelian. Now ##g## is of order ##p^k## for some ##k>0## because ##|G|=p^n##. Thus ##x \longmapsto \sigma^{p^{(k-1)}}(g)(x)=g^{p^{(k-1)}}xg^{-p^{(k-1)}}## is of order ##p##.

Now how do you know, that ##g^{p^{(k-1)}} \notin Z(G)##, because this would imply ##\sigma^{p^{(k-1)}}(g)(x)=x## and your conjugation is the identity, and thus of order one? You have it by assumption for ##k=1## but not automatically for ##k>1##.
 
  • #5
986
174
I will complete the solution of Question 9.
In my previous posts, I had done the cases of
  • G nonabelian
  • G containing cyclic group Z(pk) where k > 1

I will now consider the remaining case, G ~ (Z(p))n, a direct product of n cyclic groups Z(p). This case contains some additional automorphism elements that mix the subgroups, something true in general for repeated cyclic subgroups. For Z(p) x Z(p) with generators a and b, one can get new generators ##a \to a^s b^t## and ##b \to a^u b^v##, where at least one of s and t are nonzero mod p, at least one of u and v are nonzero mod p, and the new b is not a power of the new a. This means that for general element ##a^x b^y##, we get ##a^{sx+uy} b^{tx+vy}##. This result can be expressed in matrix form:
$$ \begin{pmatrix} x \\ y \end{pmatrix} \to \begin{pmatrix} s & u \\ t & v \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}$$
where s, t, u, and v are members of GF(p), the integers modulo p under addition and multiplication, and where the s-u-t-v matrix is nonsingular. The set of all such matrices under matrix multiplication forms a group, the general linear one with GF(p): GL(2,p). This result is easily generalized to more Z(p)'s, and Aut(Z(p)n) thus equals GL(n,p).

We continue our search for order-p automorphism elements by finding the order of this automorphism group and then using Cauchy's theorem, much like for Z(pn). The order of GL(n,p) is
$$\prod_{k=0}^{n-1} (p^n - p^k) = (p^n-1) (p^n - p) \cdots (p^n - p^{n-1}) $$
For n > 1, it is evident that this order has a factor of p in it, and by Cauchy's theorem, Aut(G) has an automorphism with order p.

This result thus covers every case where the order of G is pn with n > 1, thus showing that Aut(G) has an element with order p in every case of n > 1.
 
  • #6
Infrared
Science Advisor
Gold Member
928
518
The automorphisms of G thus include combinations of automorphisms of all these cyclic-subgroup parts. Since each such subgroup has one generator, its automorphism thus maps one of its generators onto a power of it that is relatively prime with the group's order. A combination-automorphism element of Aut(G) thus includes all of these powers.
It would be helpful if you had defined the term "combination automorphism". From context, I am guessing that it is an automorphism of the form [itex]\phi(x_1,\ldots,x_c)=(\phi_1(x_1),\ldots,\phi_c(x_c))[/itex], where each [itex]\phi_i[/itex] is an automorphism of [itex]G_c[/itex]. Is this correct?

The order of such an automorphism is the least common multiple of the orders of its automorphisms of all of the cyclic-subgroup parts. That is because each such automorphism's order must evenly divide the combination-automorphism order. So if a combination automorphism has order p, then each of the cyclic-part automorphisms must have order 1 or p.

The statement here is correct, but the explanation should be clearer. In my notation above, we can just say that [itex]\phi^t=1[/itex] if and only if [itex]\phi_i^t=1[/itex] for each [itex] i[/itex], if and only if [itex]t[/itex] is a common multiple of the orders of the [itex]\phi_i[/itex], and the claim follows.
This reduces the problem from finding an order-p automomorphism of an abelian group with power-of-p order to doing that for a cyclic group
because we can extend the automorphism to be trivial on the other factors. Also, you can't do it for a cyclic group of order [itex]p[/itex], so you mean that you've reduced the problem to this when one of the cyclic factors has order of at least [itex]p^2[/itex].
The automorphisms of a cyclic group map a generator onto all of the other generators. That is, for generator a, ##a \to a^b## for power b relatively prime to the order of the group. That means that the order of the automorphism group is the Euler totient function of the order of the group
since an automorphism is determined by where it sends a generator. Good.
In this case, ##\phi(p^n) = p^{n-1} (p -1)##. We then use Cauchy's theorem, which states that for every prime factor of the order of a group, that group contains at least one element with that prime factor as its order. For n > 1, the automorphism-group order is divisible by p, therefore the automorphism group has an element of order p.

Thus, the automorphism group of cyclic group Z(pn) for n > 1 contains an element with order p, the kind of automorphism element that we were seeking. From my discussion of combination automorphisms, this means that if G contains such a cyclic group, that subgroup can have an order-p automorphism-group element and all the others can have the identity automorphism, giving that combination automorphism order p, what we were seeking.
The argument with Cauchy's theorem is correct. It's not part of the problem, but can you explicitly write down such an element?
The last paragraph would have been better placed earlier, where you say "This reduces the problem from finding an order-p automomorphism of an abelian group with power-of-p order to doing that for a cyclic group".

Overall, it could be more clearly written at points but the correct ideas are there.
 
Last edited:
  • #7
15,415
13,436
I will complete the solution of Question 9.
In my previous posts, I had done the cases of
  • G nonabelian
  • G containing cyclic group Z(pk) where k > 1

I will now consider the remaining case, G ~ (Z(p))n, a direct product of n cyclic groups Z(p). This case contains some additional automorphism elements that mix the subgroups, something true in general for repeated cyclic subgroups. For Z(p) x Z(p) with generators a and b, one can get new generators ##a \to a^s b^t## and ##b \to a^u b^v##, where at least one of s and t are nonzero mod p, at least one of u and v are nonzero mod p, and the new b is not a power of the new a. This means that for general element ##a^x b^y##, we get ##a^{sx+uy} b^{tx+vy}##. This result can be expressed in matrix form:
$$ \begin{pmatrix} x \\ y \end{pmatrix} \to \begin{pmatrix} s & u \\ t & v \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}$$
where s, t, u, and v are members of GF(p), the integers modulo p under addition and multiplication, and where the s-u-t-v matrix is nonsingular. The set of all such matrices under matrix multiplication forms a group, the general linear one with GF(p): GL(2,p). This result is easily generalized to more Z(p)'s, and Aut(Z(p)n) thus equals GL(n,p).

We continue our search for order-p automorphism elements by finding the order of this automorphism group and then using Cauchy's theorem, much like for Z(pn). The order of GL(n,p) is
$$\prod_{k=0}^{n-1} (p^n - p^k) = (p^n-1) (p^n - p) \cdots (p^n - p^{n-1}) $$
For n > 1, it is evident that this order has a factor of p in it, and by Cauchy's theorem, Aut(G) has an automorphism with order p.

This result thus covers every case where the order of G is pn with n > 1, thus showing that Aut(G) has an element with order p in every case of n > 1.
What about cases, where no factors of ##G## are of the form ##C(p)## or if the product isn't direct?
 
  • #8
Infrared
Science Advisor
Gold Member
928
518
I will complete the solution of Question 9.
In my previous posts, I had done the cases of
  • G nonabelian
  • G containing cyclic group Z(pk) where k > 1

I will now consider the remaining case, G ~ (Z(p))n, a direct product of n cyclic groups Z(p). This case contains some additional automorphism elements that mix the subgroups, something true in general for repeated cyclic subgroups. For Z(p) x Z(p) with generators a and b, one can get new generators ##a \to a^s b^t## and ##b \to a^u b^v##, where at least one of s and t are nonzero mod p, at least one of u and v are nonzero mod p, and the new b is not a power of the new a. This means that for general element ##a^x b^y##, we get ##a^{sx+uy} b^{tx+vy}##. This result can be expressed in matrix form:
$$ \begin{pmatrix} x \\ y \end{pmatrix} \to \begin{pmatrix} s & u \\ t & v \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}$$
where s, t, u, and v are members of GF(p), the integers modulo p under addition and multiplication, and where the s-u-t-v matrix is nonsingular. The set of all such matrices under matrix multiplication forms a group, the general linear one with GF(p): GL(2,p). This result is easily generalized to more Z(p)'s, and Aut(Z(p)n) thus equals GL(n,p).

We continue our search for order-p automorphism elements by finding the order of this automorphism group and then using Cauchy's theorem, much like for Z(pn). The order of GL(n,p) is
$$\prod_{k=0}^{n-1} (p^n - p^k) = (p^n-1) (p^n - p) \cdots (p^n - p^{n-1}) $$
For n > 1, it is evident that this order has a factor of p in it, and by Cauchy's theorem, Aut(G) has an automorphism with order p.

This result thus covers every case where the order of G is pn with n > 1, thus showing that Aut(G) has an element with order p in every case of n > 1.

The argument is good, but you don't need all the background. It's good that this type of thinking helps you solve the problem, but it's out of place in a written solution. Again, it's not officially part of the problem, but maybe you'd find it fun to look for an example of such a matrix.

As @fresh_42 points out, you should say how you are getting these cases. There's a very important theorem you are implicitly using...
 
  • #9
986
174
Why can't we have a group ##G## with ##Z(G)=\{\,1\,\}\,##? And most of all: Where did you need this?
That was for giving the range of orders possible for Z(G). For G having order pn, all the conjugacy classes have orders pk, where k is between 0 and n inclusive. If the center is only the identity, then all the other elements are in classes with sizes being power of p that are at least 1. Thus, the order of the group must be mp+1 for some m, something that does not divide pn for n > 0. Meaning that is G is not the identity group, Z(G) must have an order that is at least p.

Strictly speaking, Inn(G)'s elements are all the cosets of Z(G). Thus, if an element of Inn(G) has order q, then all its coset elements taken to power q give elements of Z(G), and no smaller positive powers of them do so.

I concede that I could have come up with a simpler proof at this point. Since for nonabelian G, Inn(G) has order pk, where k > 0, it is evident that its order can be divided by p. Thus, by Cauchy's theorem, Inn(G) must contain at least one element with order p.

To summarize your proof so far:

Case 1: ##G## is not Abelian. Then there is an element ##g \in G## for which ##x \longmapsto \sigma(g)(x)=x^g=gxg^{-1}## is not the identity, for otherwise ##G## would be Abelian. Now ##g## is of order ##p^k## for some ##k>0## because ##|G|=p^n##. Thus ##x \longmapsto \sigma^{p^{(k-1)}}(g)(x)=g^{p^{(k-1)}}xg^{-p^{(k-1)}}## is of order ##p##.

Now how do you know, that ##g^{p^{(k-1)}} \notin Z(G)##, because this would imply ##\sigma^{p^{(k-1)}}(g)(x)=x## and your conjugation is the identity, and thus of order one? You have it by assumption for ##k=1## but not automatically for ##k>1##.
I get around that problem by treating Inn(G) as a black box with a certain order.
 
  • #10
986
174
It would be helpful if you had defined the term "combination automorphism". From context, I am guessing that it is an automorphism of the form [itex]\phi(x_1,\ldots,x_c)=(\phi_1(x_1),\ldots,\phi_c(x_c))[/itex], where each [itex]\phi_i[/itex] is an automorphism of [itex]G_c[/itex]. Is this correct?
That is indeed correct.
In my notation above, we can just say that [itex]\phi^t=1[/itex] if and only if [itex]\phi_i^t=1[/itex] for each [itex] i[/itex], if and only if [itex]t[/itex] is a common multiple of the orders of the [itex]\phi_i[/itex], and the claim follows.
That is indeed correct.
 
  • #11
986
174
What about cases, where no factors of ##G## are of the form ##C(p)## or if the product isn't direct?
Those cases were taken care of in my previous parts. An indirect product of cyclic factors is either nonabelian or equivalent to some other direct product. If Z(p) is absent, then G is either nonabelian or else composed of cyclic factors with higher powers of p.
 
  • #12
member 587159
Can I make an attempt at 3 before September 16? It is a problem from a previous challenge thread.
 
  • #14
member 587159
Go ahead.

I solved (a) a month ago, but didn't attempt (b) yet. Is it solvable with basic topology knowledge? (before I waste too many hours trying to solve it :P).

My idea for (b) is to show that A is clopen, and it will be the whole space then.

A technical question: can you elaborate what you mean with "each V is homeomorphocally mapped onto U by p"? All the topologies under consideration are subspace topologies?
 
  • #15
15,415
13,436
I solved (a) a month ago, but didn't attempt (b) yet. Is it solvable with basic topology knowledge? (before I waste too many hours trying to solve it :P).
Yes.
My idea for (b) is to show that A is clopen, and it will be the whole space then.
Yes, that's the idea behind the choice of ##A##. I find it still a bit tricky, but the methods are basic. You will practically only need the definition of a covering.
A technical question: can you elaborate what you mean with "each V is homeomorphocally mapped onto U by p"? All the topologies under consideration are subspace topologies?
I mean that the fibers are locally homeomorph to ##U## and disjoint. I don't see where we need subspace topologies, I think those given on ##\tilde{X}## and ##X## are all which are needed. As the fibers are disjoint, I can't see why we need to pass to the subspace topology as it is the same as the given one, i.e. it makes no difference.
 
  • #16
member 587159
Do you mean that ##p\vert_V: V \to U## is a homeomorphism for each ##V##?

Then I think that we must place subspace topologies on V and U.[/Quote]
 
Last edited by a moderator:
  • #17
15,415
13,436
Do you mean that ##p\vert_V: V \to U## is a homeomorphism for each ##V##?
All ##V_\iota \subseteq \tilde{X}## where ##p^{-1}(U)= \coprod V_\iota ## and a suitable ##U##, yes.
Then I think that we must place subspace topologies on V and U.]
Why? ##V_\iota \cap \tilde{X}=V_\iota## and ##U\in X## is open and again ##U\cap X = U##. The covering is automatically structured this way as the fibers are disjoint, and on ##X## we don't consider subspaces.
 
  • #18
member 587159
All ##V_\iota \subseteq \tilde{X}## where ##p^{-1}(U)= \coprod V_\iota ## and a suitable ##U##, yes.
Why? ##V_\iota \cap \tilde{X}=V_\iota## and ##U\in X## is open and again ##U\cap X = U##. The covering is automatically structured this way as the fibers are disjoint, and on ##X## we don't consider subspaces.

You mean that the open sets in U are those subsets of U that are also open in X? Formally, this is a subspace, as you consider a topological space on a subset of X.
 
  • #19
15,415
13,436
You mean that the open sets in U are those subsets of U that are also open in X? Formally, this is a subspace, as you consider a topological space on a subset of X.
I meant, I choose an open neighborhood of a point in ##X## which is small enough to be homeomorphic to all ##V_\iota ## and with equally many points in all fibers. It is open by choice, which I can make because of the covering property.

If I understand you right, you want to go the converse way: project open sets and build the intersection? But how should they be open if we don't have a finite covering?
 
  • #20
299
20
I have a solution for problem 1:

Let [itex]v_1,\ \ldots,\ v_k[/itex] be a basis of the range of [itex]\mathbf{X}[/itex] and extend to to a basis of [itex]\mathbb{R}^n[/itex] by adding vectors [itex]v_{k+1},\ \ldots,\ v_n[/itex]. For each [itex]i[/itex] from [itex]1[/itex] to [itex]k[/itex], choose a vector [itex]w_i[/itex] such that [itex]\mathbf{X}w_i = v_i[/itex]. Now, let [itex]f:\mathbb{R}^n \rightarrow \mathbb{R}^n[/itex] be the linear transformation defined by:

[tex]f(v_i) = \begin{cases} w_i & \text{if } i\leq k \\ 0 & \text{if } i>k \end{cases}[/tex]

Let [itex]\mathbf{Z}[/itex] be the matrix representing [itex]f[/itex]. For each [itex]i\leq k[/itex], [itex]\mathbf{XZ}v_i = \mathbf{X}w_i = v_i[/itex], and hence for every [itex]v[/itex] in the range of [itex]\mathbf{X}[/itex], [itex]\mathbf{XZ}v = v[/itex]. Therefore [itex]\mathbf{XZX} = X[/itex]

As for the trace, note that the [itex]v_i[/itex]'s form a basis of eigenvectors for [itex]\mathbf{XZ}[/itex], with the eigenvalue being [itex]1[/itex] if [itex]i\leq k[/itex] and [itex]0[/itex] otherwise, so [itex]\mathbf{XZ}[/itex] is diagonalizable and the sum of the eigenvalues is [itex]k[/itex]. Hence [itex]\mathrm{trace}(\mathbf{ZX}) = \mathrm{trace}(\mathbf{XZ}) = k = \mathrm{rank}(\mathbf{X})[/itex]. Also, since [itex]\mathbf{XZX} = X[/itex], we have automatically that [itex]\mathrm{trace}(\mathbf{ZX^3}) = \mathrm{trace}(\mathbf{XZXX}) = \mathrm{trace}(\mathbf{X^2})[/itex]. Q.E.D.
 
  • #21
StoneTemplePython
Science Advisor
Gold Member
1,203
595
I have a solution for problem 1:

Let [itex]v_1,\ \ldots,\ v_k[/itex] be a basis of the range of [itex]\mathbf{X}[/itex] and extend to to a basis of [itex]\mathbb{R}^n[/itex] by adding vectors [itex]v_{k+1},\ \ldots,\ v_n[/itex]. For each [itex]i[/itex] from [itex]1[/itex] to [itex]k[/itex], choose a vector [itex]w_i[/itex] such that [itex]\mathbf{X}w_i = v_i[/itex]. Now, let [itex]f:\mathbb{R}^n \rightarrow \mathbb{R}^n[/itex] be the linear transformation defined by:

[tex]f(v_i) = \begin{cases} w_i & \text{if } i\leq k \\ 0 & \text{if } i>k \end{cases}[/tex]

Let [itex]\mathbf{Z}[/itex] be the matrix representing [itex]f[/itex]. For each [itex]i\leq k[/itex], [itex]\mathbf{XZ}v_i = \mathbf{X}w_i = v_i[/itex], and hence for every [itex]v[/itex] in the range of [itex]\mathbf{X}[/itex], [itex]\mathbf{XZ}v = v[/itex]. Therefore [itex]\mathbf{XZX} = X[/itex]

As for the trace, note that the [itex]v_i[/itex]'s form a basis of eigenvectors for [itex]\mathbf{XZ}[/itex], with the eigenvalue being [itex]1[/itex] if [itex]i\leq k[/itex] and [itex]0[/itex] otherwise, so [itex]\mathbf{XZ}[/itex] is diagonalizable and the sum of the eigenvalues is [itex]k[/itex]. Hence [itex]\mathrm{trace}(\mathbf{ZX}) = \mathrm{trace}(\mathbf{XZ}) = k = \mathrm{rank}(\mathbf{X})[/itex]. Also, since [itex]\mathbf{XZX} = X[/itex], we have automatically that [itex]\mathrm{trace}(\mathbf{ZX^3}) = \mathrm{trace}(\mathbf{XZXX}) = \mathrm{trace}(\mathbf{X^2})[/itex]. Q.E.D.

I think this mostly works though it feels light.

Any more information on ##\mathbf Z## or these ##\mathbf w##'s? I know they exist, but I'm not totally sure how you know they do. And more to the point, the form I have in mind has a canonical relation with ##\mathbf X##.
- - - -
As for the trace equalities: the second trace equality was just a red herring that I threw in. The first one is actually a clue of sorts. If you have
##\mathbf {XZX} = \mathbf X##

and left multiply by ##\mathbf Z## you get

##\big(\mathbf {ZX}\big)^2 = \big( \mathbf {ZX}\big)##

which show that ##\big(\mathbf {ZX}\big)## is idempotent, so the trace gives it's rank. Making the link of why it is that ##\text{rank}\big(\mathbf {ZX}\big) = \text{rank}\big(\mathbf {X}\big)## explicit, would help readers I think.

- - - -
I'll remark that I found the formatting rather disorienting to read -- while some bold the matrices and some don't, I've never seen someone bold matrices and not the vectors, which then look the same as scalars.
 
  • #22
299
20
Any more information on ##\mathbf Z## or these ##\mathbf w##'s? I know they exist, but I'm not totally sure how you know they do. And more to the point, the form I have in mind has a canonical relation with ##\mathbf X##.

The ##w_i##'s exist because each ##v_i## is in the range of ##X##. Saying that there is some ##w## such that ##Xw=v## is simply what it means for v to be in the range of ##X##. I'm really not sure what more I can say on that point.

As for ##Z##, I'm just using the fact that every linear transformation between finite-dimensional vector spaces is given by some matrix (specifically, the one whose ith column is the image of the ith standard basis vector ##e_i##).

which show that ##\big(\mathbf {ZX}\big)## is idempotent, so the trace gives it's rank.

I actually hadn't noticed that the trace of an idempotent matrix is always its rank until you mentioned it just now.

Making the link of why it is that ##\text{rank}\big(\mathbf {ZX}\big) = \text{rank}\big(\mathbf {X}\big)## explicit, would help readers I think.

I was actually using the matrix ##XZ##, along with the identity ##\mathrm{trace}(AB) = \mathrm{trace}(BA)##. As for why the rank of ##XZ## matches the rank of ##X##, this is because the range of ##XZ## matches the range of ##X##. Indeed, the range of ##XZ## is always contained in the range of ##X##, and I specifically defined ##Z## so that ##XZ## would be the identity on the range of ##X##, so the range will contain the range of ##X##.

I'll remark that I found the formatting rather disorienting to read -- while some bold the matrices and some don't, I've never seen someone bold matrices and not the vectors, which then look the same as scalars.

Sorry, I was just trying to match the formatting of the original problem. :sorry: I normally don't bold the matrices either, since being capitalized is sufficient indication that they are matrices.
 
  • #23
StoneTemplePython
Science Advisor
Gold Member
1,203
595
working backwards:

I actually hadn't noticed that the trace of an idempotent matrix is always its rank until you mentioned it just now.

This is a very big deal. See e.g. the top answer here
https://mathoverflow.net/questions/13526/geometric-interpretation-of-trace
- - - -
The problem is quite simple once you've broken the abstraction -- I was hoping people would be able to glean a couple insights from it. This is one of them.

Regarding the second insight:
The ##w_i##'s exist because each ##v_i## is in the range of ##X##. Saying that there is some ##w## such that ##Xw=v## is simply what it means for v to be in the range of ##X##. I'm really not sure what more I can say on that point.

As for ##Z##, I'm just using the fact that every linear transformation between finite-dimensional vector spaces is given by some matrix (specifically, the one whose ith column is the image of the ith standard basis vector ##e_i##).

By analogy: I suppose it's a bit like solving for a valid ##\mathbf x## in ##\mathbf{Ax} = \mathbf b## where ##\mathbf A## is short and fat with full row rank. There are many different ways to come up with a valid ##\mathbf x## (or more weakly: show that a solution exists by pointing out that column rank = row rank), but the most insightful and pleasant one is the one with minimum length (2 norm) ##\mathbf x = \mathbf A^T\big(\mathbf{AA}^T\big)^{-1}b##.

The most insightful and pleasant answer to this problem is the one with minimum length (Frobenius norm) ##\big(\mathbf {ZX}\big)##. My sense is such a solution is within your reach, but I don't want it to seem like I'm moving the goalposts after you've kicked the ball-- the original problem statement did not require this. I suppose we can append it as a 3rd part if needed.
 
  • #24
299
20
By analogy: I suppose it's a bit like solving for a valid ##\mathbf x## in ##\mathbf{Ax} = \mathbf b## where ##\mathbf A## is short and fat with full row rank. There are many different ways to come up with a valid ##\mathbf x## (or more weakly: show that a solution exists by pointing out that column rank = row rank), but the most insightful and pleasant one is the one with minimum length (2 norm) ##\mathbf x = \mathbf A^T\big(\mathbf{AA}^T\big)^{-1}b##.

Hmm... you and I have very different intuitions about what the most insightful solution is. I would consider mentioning that column rank = row rank to be far more insightful than offering a formula for the solution, since it tells us why there is a solution in the first place. Additionally, it has the advantage of generalizing to arbitrary fields, whereas the formula you gave only works on ordered fields (and the complex numbers, if transpose is replaced with conjugate transpose).

The most insightful and pleasant answer to this problem is the one with minimum length (Frobenius norm) ##\big(\mathbf {ZX}\big)##. My sense is such a solution is within your reach, but I don't want it to seem like I'm moving the goalposts after you've kicked the ball-- the original problem statement did not require this. I suppose we can append it as a 3rd part if needed.

Yeah, you should probably do that. After some googling, I came across the
Moore–Penrose pseudoinverse
, and I figure that's the solution you were looking for. As such, I would have to disqualify myself from participating the third part, since I now already know the answer.
 
  • #25
627
422
Pardon the offtopic.
I find the introduction in the first post a bit strange. Summer is long gone now :DD Or you could be talking about summer 2019 or the folks that live their lives upside down.
 

Related Threads on Intermediate Math Challenge - September 2018

Replies
38
Views
4K
Replies
16
Views
4K
Replies
20
Views
3K
Replies
61
Views
7K
Replies
55
Views
6K
Replies
39
Views
8K
Replies
52
Views
7K
  • Sticky
  • Last Post
4
Replies
84
Views
1K
Replies
67
Views
8K
Replies
71
Views
7K
Top