Math Challenge - July 2023

[Infrared]

Welcome to this month's math challenge thread!

Rules:
1. You may use google to look for anything except the actual problems themselves (or very close relatives).
2. Do not cite theorems that trivialize the problem you're solving.
3. Have fun!

1. (solved by @AndreasC) I start watching a stream from my favorite youtuber 10 minutes after the stream starts. To catch up to the stream, I make the playback speed 1.5x. How long will it take until I am caught up with the stream?

2. (solved by @julian) Evaluate the following limit:
$$\lim_{x\to\infty} e^{-\sqrt{x}}\left(1+\frac{1}{\sqrt{x}}\right)^x.$$

3. (solved by @julian) Evaluate $\int_0^1\frac{1-x^2}{\ln(x)} dx.$

4. (solved by @AndreasC) If $T:V\to V$ and $S:W\to W$ are linear maps with eigenvalues $\alpha$ and $\beta$, respectively, check that $\alpha\beta$ is an eigenvalue of $T\otimes S:V\otimes W\to V\otimes W.$ Since every polynomial is the characterstic polynomial of a linear map (up to scalar multiplication), conclude that the product of two algebraic numbers is algebraic. Construct a linear transformation on $V\otimes W$ with eigenvalue $\alpha+\beta$ to show that the sum of two algebraic numbers is algebraic.

5. (solved by @mathwonk) Let $A$ be an $n\times m$ matrix with rank $r$ and let $B$ be a $p\times q$ matrix with rank $s.$ Consider the set of all $m\times p$ matrices $X$ satisfying $AXB=0.$ This set is a vector space. What is its dimension?

6. What is the smallest positive integer $m$ such that there exist integer polynomials $p_1(x),\ldots,p_n(x)$ with $mx=p_1(x)^3+\ldots+p_n(x)^3.$

7. (solved by @mathwonk)Give examples of groups $G$ and $H$ such that $G$ contains a subgroup isomorphic to $H$ and $H$ contains a subgroup isomorphic to $G$, but $G$ is not isomorphic to $H.$

8. (solved by @AndreasC) Let $A$ be an $n\times n$ matrix all of whose entries are non-negative real numbers. Show that $A$ has a non-negative real eigenvalue.

9. (solved for $n=2$ by @AndreasC and @mathwonk. (Solved for $n>2$ by @mathwonk) Let $f:\mathbb{R}^n\to\mathbb{R}^n$ be a continuous function such that $f(f(x))=x$ for all $x\in\mathbb{R}^n.$ Does $f$ necessarily have a fixed point?

 

[julian]

#2

Spoiler

We have

\begin{align*}
\lim_{x \rightarrow \infty} \ln (e^{-\sqrt{x}} \left( 1 + \frac{1}{\sqrt{x}} \right)^{x} ) & = \lim_{x \rightarrow \infty} (x \ln (1 + \frac{1}{\sqrt{x}}) - \sqrt{x})
\nonumber \\
& = \lim_{x \rightarrow \infty} (x(\frac{1}{\sqrt{x}} - \frac{1}{2x} + \dots) - \sqrt{x})
\nonumber \\
& = - \frac{1}{2}
\end{align*}

As

\begin{align*}
\lim_{x \rightarrow \infty} e^{f(x)} = \exp (\lim_{x \rightarrow \infty} f(x))
\end{align*}

we have

\begin{align*}
\lim_{x \rightarrow \infty} e^{-\sqrt{x}} \left( 1 + \frac{1}{\sqrt{x}} \right)^{x} = \frac{1}{\sqrt{e}}
\end{align*}

 

[julian]

#3

Spoiler

Write

\begin{align*}
I (\alpha) & = \int_0^1 \dfrac{1 - x^\alpha}{\ln x} dx
\nonumber \\
& = \int_0^1 \dfrac{1 - e^{\alpha \ln x}}{\ln x} dx
\end{align*}

So that

\begin{align*}
\frac{\partial I (\alpha)}{\partial \alpha} & = \frac{\partial}{\partial \alpha} \int_0^1 \dfrac{1 - e^{\alpha \ln x} }{\ln x} dx
\nonumber \\
& = - \int_0^1 e^{\alpha \ln x} dx
\nonumber \\
& = - \int_0^1 x^\alpha dx .
\end{align*}

Performing the integral we obtain:

\begin{align*}
\frac{\partial I (\alpha)}{\partial \alpha} = - \frac{1}{1 + \alpha}
\end{align*}

Implying

\begin{align*}
I (\alpha) = - \ln (1 + \alpha) + C
\end{align*}

Putting $\alpha = 0$ we have $I(0) = 0$. So that $C = 0$, and so

\begin{align*}
\int_0^1 \dfrac{1 - x^2}{\ln x} dx = - \ln 3 .
\end{align*}

 

[Throwaway_for_June]

Is Brouwer's fixed point theorem considered to be trivializing #9?

 

[AndreasC]

Well, #1 is simple... Surprised nobody bothered with it yet.

Spoiler: Problem #1

1.5x means you are watching 1.5 seconds of material every second. To catch up, you get the equation:

$$t+10=1.5t$$

Solving it, it's 20 minutes.

 

[Infrared]

Well, #1 is simple... Surprised nobody bothered with it yet.

Yes, this one is definitely easier. I intended it for any younger students who are here. Of course your answer is right.

 

[AndreasC]

Is Brouwer's fixed point theorem considered to be trivializing #9?

Brouwer needs a compact convex set. What compact convex set does it necessarily map to itself?

 

[AndreasC]

Yes, this one is quite easy. I intended it for any younger students who are here. Of course your answer is right.

Well there's gotta be something I can solve lol

 

[Infrared]

Is Brouwer's fixed point theorem considered to be trivializing #9?

You can use Brouwer. Maybe a rule of thumb: if just stating the theorem you're using would count as a proof, then it's in appropriate to cite, and otherwise it's okay.

 

[AndreasC]

Well, if we are using Brouwer for problem #9:

Spoiler

The function is invertible, so it is injective, and also can take any value in the real numbers, therefore also surjective. Suppose that x and f(x) are not the same (otherwise that is a fixed point). Then these points form an interval, and are mapped to f(x) and x. Because it is bijective and continuous (therefore also strictly monotone etc etc), we see that every point in the interval has to be mapped to points between these two. So the (compact) interval with endpoints x and f(x) is mapped to itself. According to Brouwer's fixed point theorem, the function has a fixed point inside the interval.

 

[Infrared]

Well, if we are using Brouwer for problem #9:

Spoiler

The function is invertible, so it is injective, and also can take any value in the real numbers, therefore also surjective. Suppose that x and f(x) are not the same (otherwise that is a fixed point). Then these points form an interval, and are mapped to f(x) and x. Because it is bijective and continuous, we see that every point in the interval has to be mapped to points between these two. So the (compact) interval with endpoints x and f(x) is mapped to itself. According to Brouwer's fixed point theorem, the function has a fixed point inside the interval. [\SPOILER]

The function is from $\mathbb{R}^n$ to $\mathbb{R}^n$, not from $\mathbb{R}$ to $\mathbb{R}.$

 

[AndreasC]

The function is from $\mathbb{R}^n$ to $\mathbb{R}^n$, not from $\mathbb{R}$ to $\mathbb{R}.$

Ohh apologies, I didn't notice.

 

[AndreasC]

Ok, looking once again at #9 after reading it correctly, I think I came up with a cool answer.

EDIT: Nvm it was completely wrong lol

 

[AndreasC]

Well, now I at least have an idea to solve #8. I will only sketch it without proving too much because I'm on a phone, but I believe it's basically right:

Spoiler: Problem #8

Suppose it has no 0 eigenvalues (if it does, well, it's obvious). The matrix is a continuous, linear, 1-1 map from $\mathbb{R}^n$ to $\mathbb{R}^n$, ie a homeomorphism. As a map, we call it $A(x)$. We can quotient out rays by projecting them onto the unit sphere, excluding the point 0. Because it is linear, it maps rays to rays. Therefore, the projection onto the unit sphere induces a new continuous map $\tilde{A}$ from the unit sphere to the unit sphere. It also maps the set of non-zero points with non-negative coefficients to themselves. Therefore, $\tilde{A}$ maps the section of the unit sphere with non-negative coordinates to itself. This section is homeomorphic to the (n-1)-dimensional closed disk, which is compact and convex. Using Brouwer, we get a fixed point, which corresponds to $A$ sending a ray to itself. But then every vector on that ray is an eigenvector with a positive eigenvalue, QED.

 

[wrobel]

Is Brouwer's fixed point theorem considered to be trivializing #9?

You can use Brouwer. Maybe a rule of thumb: if just stating the theorem you're using would count as a proof, then it's in appropriate to cite, and otherwise it's okay.

I am very interesting how to prove existence of a fixed point in #9. Looking forward to seeing the solution.

 

[nuuskur]

#8 The trace, i.e, the sum of all eigenvalues of $A$ is nonnegative. If all eigenvalues were real, there has to be one that is nonnegative - so we may assume $A$ is not symmetric. Otherwise, we'd need to show that (in 3x3 case, for instance) stuff like $\lambda _1 = a<0$ and $\lambda _{2,3} = b \pm ic$, where $b>-a/2$, can't happen. Perron-Frobenius does suffice, but I'd like to see if there is a purely algebraic approach.

 

[AndreasC]

#8 The trace, i.e, the sum of all eigenvalues of $A$ is nonnegative. If all eigenvalues were real, there has to be one that is nonnegative - so we may assume $A$ is not symmetric. Otherwise, we'd need to show that (in 3x3 case, for instance) stuff like $\lambda _1 = a<0$ and $\lambda _{2,3} = b \pm ic$, where $b>-a/2$, can't happen. Perron-Frobenius does suffice, but I'd like to see if there is a purely algebraic approach.

What do you think of my topological solution?

 

[Infrared]

Well, now I at least have an idea to solve #8. I will only sketch it without proving too much because I'm on a phone, but I believe it's basically right:

Spoiler: Problem #8

Suppose it has no 0 eigenvalues (if it does, well, it's obvious). The matrix is a continuous, linear, 1-1 map from $\mathbb{R}^n$ to $\mathbb{R}^n$, ie a homeomorphism. As a map, we call it $A(x)$. We can quotient out rays by projecting them onto the unit sphere, excluding the point 0. Because it is linear, it maps rays to rays. Therefore, the projection onto the unit sphere induces a new continuous map $\tilde{A}$ from the unit sphere to the unit sphere. It also maps the set of non-zero points with non-negative coefficients to themselves. Therefore, $\tilde{A}$ maps the section of the unit sphere with non-negative coordinates to itself. This section is homeomorphic to the (n-1)-dimensional closed disk, which is compact and convex. Using Brouwer, we get a fixed point, which corresponds to $A$ sending a ray to itself. But then every vector on that ray is an eigenvector with a positive eigenvalue, QED.

Very nice! This is basically the solution that I had in mind. I had this assigned as a homework problem back when I took topology in undergrad and it quite impressed me that Brouwer could be used this way.

 

[Throwaway_for_June]

...I'd like to see if there is a purely algebraic approach.

It seems like there should be an argument based on applying some kind of power iteration algorithm (https://en.wikipedia.org/wiki/Power_iteration) to vectors with non-negative coefficients.

 

[AndreasC]

Very nice! This is basically the solution that I had in mind. I had this assigned as a homework problem back when I took topology in undergrad and it quite impressed me that Brouwer could be used this way.

Brouwer can really be used to prove anything huh?

 

[Gear300]

#6

Spoiler: spoiler

Writing each polynomial out as
$$
p_i(x)^3
= \big( \sum_{k=0}^{m_i} a_{ik} x^k \big)^3 ~,
$$
the coefficient on the first order term will have to be $\binom{3}{1}a_{i1}a_{i0}^2$. Hence the first order coefficient in the sum of polynomials right of equality will be
$$
\sum_i \binom{3}{1} a_{i1}a_{i0}^2
= 3 \sum_i a_{i1}a_{i0}^2 ~.
$$
So the smallest positive integer value $m$ can take is 3.

 

[Infrared]

#6

Spoiler: spoiler

Writing each polynomial out as
$$
p_i(x)^3
= \big( \sum_{k=0}^{m_i} a_{ik} x^k \big)^3 ~,
$$
the coefficient on the first order term will have to be $\binom{3}{1}a_{i1}a_{i0}^2$. Hence the first order coefficient in the sum of polynomials right of equality will be
$$
\sum_i \binom{3}{1} a_{i1}a_{i0}^2
= 3 \sum_i a_{i1}a_{i0}^2 ~.
$$
So the smallest positive integer value $m$ can take is 3.

This shows that $m$ has to be a multiple of $3$ but it doesn't show that it's actually possible to attain $m=3.$

 

[Gear300]

This shows that $m$ has to be a multiple of $3$ but it doesn't show that it's actually possible to attain $m=3.$

Not to leave it hanging. $p_1, p_2, p_3$ such that $a_{10}=a_{20}=a_{30}=1$ and $a_{11}=a_{12}=1$, $a_{13}=-1$ should work.

 

[Infrared]

Not to leave it hanging. $p_1, p_2, p_3$ such that $a_{10}=a_{20}=a_{30}=1$ and $a_{11}=a_{12}=1$, $a_{13}=-1$ should work.

The problem is not for the $x$ coefficient of $p_1(x)^3+\ldots+p_n(x)^3$ to be $m$, but for it to actually equal $mx.$

 

[AndreasC]

I don't understand #4. Take V=W=R. Take (2) and (3) linear maps on R. Their tensor product has exactly 2 eigenvalues, 2 and 3. Not 6. Doesn't this go contrary to the statement of the problem?

 

[Infrared]

I don't understand #4. Take V=W=R. Take (2) and (3) linear maps on R. Their tensor product has exactly 2 eigenvalues, 2 and 3. Not 6. Doesn't this go contrary to the statement of the problem?

$\left((2)\otimes (3)\right) (1\otimes 1)= 2\otimes 3=6 (1\otimes 1).$
Anyway $\mathbb{R}\otimes_\mathbb{R}\mathbb{R}$ is a 1-dimensional vector space over $\mathbb{R},$ so definitely no linear map on it can have two distinct eigenvalues.

Edit: Maybe you're confusing tensor product with direct product or direct sum?

 

[AndreasC]

$\left((2)\otimes (3)\right) (1\otimes 1)= 2\otimes 3=6 (1\otimes 1).$
Anyway $\mathbb{R}\otimes_\mathbb{R}\mathbb{R}$ is a 1-dimensional vector space over $\mathbb{R},$ so definitely no linear map on it can have two distinct eigenvalues.

Edit: Maybe you're confusing tensor product with direct product or direct sum?

Oof you are right, I keep confusing them...

 

[Gear300]

The problem is not for the $x$ coefficient of $p_1(x)^3+\ldots+p_n(x)^3$ to be $m$, but for it to actually equal $mx.$

Ah that's right, $\sum_i a_{i0}^3 = 0$ should hold . Using only first order polynomials, there are four equations,
$$
\sum_i a_{i0}^3 = 0 ~,
\quad
3 \sum_i a_{i1}a_{i0}^2 = m ~,
\quad
3 \sum_i a_{i0}a_{i1}^2 = 0 ~,
\quad
\sum_i a_{i1}^3 = 0 ~.
$$

 

[AndreasC]

Problem #4 seems also straightforward:

Spoiler

If v is the eigenvector with eigenvalue α and w the one with β, then $v \xtimes w$ has eigenvalue αβ.

If α is algebraic then it is the root of some polynomial with rational coefficients, which can be written as the characteristic polynomial of a map T. Same for β and S. Their tensor product has αβ as an eigenvalue, so it is a root of its characteristic polynomial, which also has rational coefficients.

For the other thing, get the tensor product of T and the identity, add it to the tensor product of the identity and S, and use the same eigenvector, and you got it.

 

[Infrared]

@AndreasC That is right. The one thing which I think should be added is that if linear maps $T:V\to V$ and $S:W\to W$ are represented by matrices $A$ and $B$ in bases $\{v_i\}$ and $\{w_j\}$ then the matrix of $T\otimes S$ in the basis $\{v_i\otimes w_j\}$ is the Kronecker product of $A$ and $B.$ This is needed to say why the matrix of the tensor product has rational entries, so the roots of its characteristic polynomial are algebraic numbers. And maybe also you could describe how to get any rational polynomial as the characteristic polynomial (up to scaling!) of a rational matrix, but this construction is pretty well known.

Edit: I guess it's not actually necessary to explain the Kronecker product. If you consider $V$ and $W$ to be vector spaces over $\mathbb{Q}$ then $V\otimes_\mathbb{Q} W$ is too so any linear transformation on it will be represented by a matrix with rational entries.

 

[AndreasC]

It is kind of insane to me that #7 could possibly have a solution... Thus far all I have figured out is that it is definitely an infinite group, and obviously the subgroups have to be proper... But that is simple, I can't think of what it might be however.

Similarly, #9 is bothering me a lot. I tried to use Brouwer like I used for the n=1 case, but while I can easily come up with a compact set that is mapped to itself, coming up with a convex one is hard.

 

[wrobel]

the set in Brouwer theo. can only be homeomorphic or even it can be a retraction to (of) the convex one but it does not help me. I do not see any suitable invariant compact sets

 

[AndreasC]

the set in Brouwer theo. can only be homeomorphic or even it can be a retraction to (of) the convex one but it does not help me

Right. I have an idea for n=2 as well. But I find it kinda hard to generalize it.

 

[AndreasC]

I can prove #9 if I could prove several other hunches I have that probably have to do with algebraic topology (which I don't really know much at all about).

I will lay out my idea here, and maybe someone can do something with it. My goal is to come up with a set homeomorphic to a compact convex set that is mapped to itself. If that is done, then Brouwer settles it.

The idea is, I take a point, say 0. Assume it is not fixed. Then f(0) is some other point. I include them both in one compact, convex set, call it A. Then f(A) has a non-zero intersection with A, and the union of these sets is also compact, and mapped to itself.

This union in general has a hole, similar to the hole in a torus, but it is simply connected. That is, we can contract the subspace into a closed loop-like object, or something higher dimensional.

We can close the holes using other compact sets. We thus get another closed set that is homeomorphic to a convex one, call it A'. Take its union with f(A'). This time, their union again may not be contractible to a point (so homeomorphic to a convex set, at least that's my assertion), if it has a hole then it is a higher dimensional hole, that is, it contracts to something like a typical 2-sphere, or something higher dimensional. Not sure how to prove it, but I'm guessing it has something to do with the fact that the interection of the two (contractible to a point) sets is now simply connected. If we do this process again then the intersection will not just be simply connected, but also contractible to a loop at worst, etc. That's my hunch.

We can continue doing this, until we have no dimensions left in the space. Every time the hole goes up at least one dimension, if one exists. So if its dimension would have to be greater than n, then we can conclude that there is no hole any more.

In the case where n=1, the set we are looking for is the union of A and f(A). In the case where n=2, we need f(A') and A', etc.

 

[mathwonk]

@AndreasC: What about this version of your idea? choose any point p in the plane, and join p to f(p) by a line segment L. Then consider the simple closed curve f(L). If L meets f(L) only at the endpoints, then their union bounds a compact set K homeomorphic to a disc. Then K must be mapped to a compact connected set with the same boundary curve, hence to itself. Apply Brouwer to K.

If L does meet f(L), choose a point q on L such that f(q) is also on L, and the distance from q to f(q) is minimal. Let M be the sub line segment joining q to f(q). Then no interior point of M can map to a point of M, i.e. M and f(M) meet only at endpoints, so apply the earlier argument to the set bounded by M union f(M).