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

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

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

2019-20 Presentation complex

Let \(G = (S | R)\) be a group presentation where S is a set of generators and R is a set of relators. Given any subset S’ of S, we set R’ to be the subset of R which consists of words only in the elements of S’. Then the presentation \(S’|R’\) is called a sub-presentation of \(S|R\).

The presentation complex for the presentation \(S|R\) is a cell complex constructed as follows: start with a single vertex v. For each element s of S, we attach an oriented edge labelled by s to v by identifying both endpoints of the edge with v. In this way, we get a wedge of circles where the circles are in 1-1 correspondence with the generating set S. For each element r of R, we attach a closed disk to the wedge of circles we obtained so that the boundary of the disk after gluing can be read using the labels of the edges to be the word r we started with.

For instance, consider the following presentation of a group \(x, y| xyx^{-1}y^{-1}\). We get a wedge of two circles first labelled by x and y. Then we add one disk so that the boundary reads as \(xyx^{-1}y^{-1}\). It is easy to see that the resulting space is homeomorphic to the torus. As one sees from this example, the presentation complex is a cell complex whose fundamental group is the group with the given presentation. For a group presentation \((S|R)\), let \( K(S|R) \) denote the presentation complex.

Suppose we have a group presentation \((S|R)\) such that any continuous map \(f: S^2 \to K(S|R) \) is homotopic to a constant map where \(S^2\) is the 2-sphere. Prove or find a counter-example to that every sub-presentation of \((S|R)\) has the same property, i.e., for any sub-presentation \((S|R)\), every continuous map \(h: S^2 \to K(S’|R’)\) is homotopic to a constant map.

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