# Solution: 2020-02 union of subgroups

Either find an example of a group which is expressed as the union of two proper subgroups or prove that such a group cannot exist.

The best solution was submitted by 고성훈 (수리과학과 2018학번). Congratulations!

Here is his solution of problem 2020-02.

Other solutions were submitted by 구은한 (수리과학과 2019학번, +3), 김기수 (수리과학과 2018학번, +3), 김동률 (수리과학과 2015학번, +3), 박현영 (전기및전자공학부 2016학번, +3), 유찬진 (수리과학과 2015학번, +3), 이준호 (2016학번, +3), 장우영 (서울대 경제학과, +3).

GD Star Rating

# Solution: 2020-01 Another singular matrix

For a given positive integer $$n$$, find all non-negative integers $$r$$ such that the following statement holds:

For any real $$n \times n$$ matrix $$A$$ with rank $$r$$, there exists a real $$n \times n$$ matrix $$B$$ such that $$\det (AB+BA) \neq 0$$.

The best solution was submitted by 홍의천 (수리과학과 2017학번). Congratulations!

Below is his solution (in text) of problem 2020-01.

An incomplete solutions was submitted by 고성훈(수리과학과 2018학번, +2).

Let’s prove the statement in the problem holds if and only if 2r>=n.
Let V=R^n and think of n*n real matrices as linear operators on V.

AB(V) and A(V), so also BA(V) has dimension at most r.
(AB+BA)(V) has dimension at most 2r so if the statement holds then 2r>=n.

Let’s assume that 2r>=n.
Let the null space and range of A be U and W, respectively, and X the intersection of the two.
Let {a_1, a_2, … , a_k}, {a_1, a_2, … , a_k, b_1, b_2, … , b_(n-r-k)},
{a_1, a_2, … , a_k, c_1, c_2, … , c_(r-k)} be bases for X, U, W, respectively.
The subspace spanned by {c_1, c_2, … , c_(n-r-k)} (here we use 2r>=n) does not contain
a non-zero element of U so {d_1, d_2, … , d_(n-r-k)}
(d_i=A(c_i), 1<=i<=n-r-k) is linearly independent.
Let {d_1, d_2, … , d_(n-r-k), e_1, e_2, … , e_(2r-n+k)} be another basis for W.
The subspace spanned by {b_1, b_2, … , b_(n-r-k)} does not contain a non-zero element of W
so {b_1, b_2, … , b_(n-r-k), d_1, d_2, … , d_(n-r-k), e_1, e_2, … , e_(2r-n+k)}
is linearly independent and we may obtain a basis for V by adding f_1, f_2, … , f_k.

Let’s define B by determining it’s values on the basis elements.
Set B(b_i) (1<=i<=n-r-k) so that AB(b_i)=c_i (which is possible since c_i is in W),
let B(d_i)=c_i+b_i (1<=i<=n-r-k) (so that AB(d_i)=d_i),
set B(e_i) (1<=i<=2r-n+k) so that AB(e_i)=e_i,
let B(f_i)=0 (1<=i<=k).
Then for any w in W, AB(w)=w.

Let’s show the range of AB+BA is the whole of V.
For 1<=i<=n-r-k, (AB+BA)(b_i)=c_i+B(0)=c_i, (AB+BA)(c_i)=c_i+B(d_i)=2c_i+b_i
so b_i is in the range of AB+BA.
For any x in X, (AB+BA)(x)=x+B(0)=x and so U is in the range of AB+BA.
For any v in V, ABA(v)=A(v) so BA(v)-v is in U.
For any w in W, (AB+BA)(w)-2w=BA(w)-w is in U so W is in the range of AB+BA.
For any v in V, (AB+BA)(v)-AB(v)-v=BA(v)-v is in U so v is in the range of AB+BA.
The whole of V is in the range of AB+BA so det(AB+BA) is not zero.

GD Star Rating

# Solution: 2019-21 Approximate isometry

Let $$A$$ be an $$m \times n$$ matrix and $$\delta \in (0, 1)$$. Suppose that $$\| A^T A – I \| \leq \delta$$. Prove that all singular values of $$A$$ are contained in the interval $$(1-\delta, 1+\delta)$$.

The best solution was submitted by 고성훈 (수리과학과 2018학번). Congratulations!

Here is his solution of problem 2019-21.

A similar solution was submitted by 김태균 (수리과학과 2016학번, +3). Incomplete solutions was submitted by 박재원 (2019학번, +2), 하석민 (수리과학과 2017학번, +2).

GD Star Rating

# Solution: 2019-19 Balancing consecutive squares

Find all integers $$n$$ such that the following holds:

There exists a set of $$2n$$ consecutive squares $$S = \{ (m+1)^2, (m+2)^2, \dots, (m+2n)^2 \}$$ ($$m$$ is a nonnegative integer) such that $$S = A \cup B$$ for some $$A$$ and $$B$$ with $$|A| = |B| = n$$ and the sum of elements in $$A$$ is equal to the sum of elements in $$B$$.

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2019-19.

An incorrect solution was submitted.

GD Star Rating

# Solution: 2019-17 0.7?

Let $$n \in \mathbb{Z}^+$$ and $$x, y \in \mathbb{R}^+$$ such that $$x^n + y^n = 1$$. Prove that
$(1-x)(1-y) \left( \sum_{k=1}^n \frac{1+x^{2k}}{1+x^{4k}} \right) \left( \sum_{k=1}^n \frac{1+y^{2k}}{1+y^{4k}} \right) < \frac{7}{10}.$

The best solution was submitted by 하석민 (수리과학과 2017학번). Congratulations!

Here is his solution of problem 2019-17.

Another solution was submitted by 채지석 (수리과학과 2016학번, +3).

GD Star Rating

# Solution: 2019-16 Groups with abundant quotients

Suppose a group $$G$$ has a finite index subgroup that maps onto the free group of rank 2. Show that every countable group can be embedded in one of the quotient groups of $$G$$.

The best solution was submitted by 하석민 (수리과학과 2017학번). Congratulations!

Here is his solution of problem 2019-16.

GD Star Rating

# Solution: 2019-15 Singular matrix

Let $$A, B$$ be $$n \times n$$ Hermitian matrices. Find all positive integer $$n$$ such that the following statement holds:

“If $$AB – BA$$ is singular, then $$A$$ and $$B$$ have a common eigenvector.”

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2019-14.

A similar solution was submitted by 하석민 (수리과학과 2017학번, +3). Late solutions are not graded.

GD Star Rating

# Solution: 2019-14 Residual finite groups

A group $$G$$ is called residually finite if for any nontrivial element $$g$$ of $$G$$, there exists a finite group $$K$$ and a surjective homomorphism $$\rho: G \to K$$ such that $$\rho(g)$$ is a nontrivial element of $$K$$.

Suppose $$G$$ is a finitely generated residually finite group. Show that any surjective homomorphism from $$G$$ to itself is an isomorphism.

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2019-14.

Other solutions were submitted by 김동률 (수리과학과 2015학번, +3), 김태균 (수리과학과 2016학번, +3), 하석민 (수리과학과 2017학번, +3).

GD Star Rating

# Solution: 2019-12 Groups generated by two homeomorphisms of the real line

Let $$I, J$$ be connected open intervals such that $$I \cap J$$ is a nonempty proper sub-interval of both $$I$$ and$$J$$. For instance, $$I = (0, 2)$$ and $$J = (1, 3)$$ form an example.

Let $$f$$ ($$g$$, resp.) be an orientation-preserving homeomorphism of the real line $$\mathbb{R}$$ such that the set of points of $$\mathbb{R}$$ which are not fixed by $$f$$ ($$g$$, resp.) is precisely $$I$$ ($$J$$, resp.).

Show that for large enough integer $$n$$, the group generated by $$f^n, g^n$$ is isomorphic to the group with the following presentation

$<a, b | [ab^{-1}, a^{-1}ba] = [ab^{-1}, a^{-2}ba^2] = id>.$

The best solution was submitted by 김동률 (수리과학과 2015학번). Congratulations!

Here is his solution of problem 2019-12.

GD Star Rating

# Solution: 2019-13 Property R

Let $$A_{a, b} = \{ (x, y) \in \mathbb{Z}^2 : 1 \leq x \leq a, 1 \leq y \leq b \}$$. Consider the following property, which we call Property R:

“If each of the points in $$A$$ is colored red, blue, or yellow, then there is a rectangle whose sides are parallel to the axes and vertices have the same color.”

Find the maximum of $$|A_{a, b}|$$ such that $$A_{a, b}$$ has Property R but $$A_{a-1, b}$$ and $$A_{a, b-1}$$ do not.

The best solution was submitted by 하석민 (수리과학과 2017학번). Congratulations!

Here is his solution of problem 2019-13.