Category Archives: solution

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
loading...

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
loading...

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
loading...

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
loading...

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
loading...

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
loading...

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
loading...

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
loading...

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
loading...

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.

An incorrect solution was received. Late solutions are not graded.

GD Star Rating
loading...