# 2020-03 Graceful permutations

A permutation $$\pi : [n]\rightarrow [n]$$ is graceful if $$|\pi(i+1) – \pi(i)| \neq |\pi(j+1)-\pi(j)|$$ for all $$i\neq j \in [n-1]$$. For a graceful permutation $$\pi :[2k+1] \rightarrow [2k+1]$$ with $$\pi(\{2,4,\dots,2k\}) = [k]$$, prove that $$\pi(1)+ \pi(2k+1) = 3k+2$$.

GD Star Rating

# 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

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

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

# 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$$.

GD Star Rating

# Notice: 2020 spring semester

POW in 2020 spring semester will begin this Friday (3/20).

GD Star Rating

# 2019-22 Prime divisors of polynomial iterates

Let $$f = X^n + a_{n-1}X^{n-1} + \dots + a_0\in \mathbb{Z}[X]$$ be a polynomial with integer coefficients, and let $$m\in \mathbb{Z}$$.

Consider the sequence $f_0,f_1,f_2,\dots$

where $$f_0:=m$$, and $$f_i:=f(f_{i-1})$$ for all $$i\ge 1$$.

Let $$S:=\{p\in \mathbb{P}: p \text{ divides } f_i \text{ for some } i\ge 0\}$$ be the set of prime divisors of the sequence $$f_0,f_1,f_2,\dots$$.

Assume that $$S$$ is finite, but $$\{f_i\mid i\ge 0\}$$ is infinite. Show that $$f=X^n$$.

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

# 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)$$.

GD Star Rating