linear algebra | Beni Bogoşel's blog

IMC 2020 Day 1 – Some Hints for Problems 1-2

August 31, 2020 beni22sof 1 comment

Problem 1. Let ${n}$ be a positive integer. Compute the number of words ${w}$ (finite sequences of letters) that satisfy all the following requirements: (1) ${w}$ consists of ${n}$ letters, all of them from the alphabet ${\{a,b,c,d\}}$ (2) ${w}$ contains an even number of letters ${a}$ (3) ${w}$ contains an even number of letters ${b}$ (For example, for ${n=2}$ there are ${6}$ such words: ${aa, bb, cc,dd,cd}$ and ${dc}$ .)

(proposed by Armend Sh. Shabani, University of Prishtina)

Hint: In order to get a formula for the total number of words it is enough to note that the even number $2k$ of a’s can be distributed in ${n\choose 2k}$ ways among the possible positions, and the even number of $2l$ b’s can be distributed in ${n-2k\choose 2l}$ ways among the remaining positions. Once the a’s and b’s are there, the rest can be filled with c’s and d’s in $2^{n-2k-2l}$ ways. This gives

$\displaystyle \sum_{k=0}^{n/2} \sum_{l=0}^{n/2-k}{n\choose 2k}{n-2k\choose 2l}2^{n-2k-2l}$

Next, use some tricks regarding expansions of $(a+b)^n+(a-b)^n$ to compress the sum above to $4^{n-1}+2^{n-1}$ .

Problem 2. Let ${A}$ and ${B}$ be ${n\times n}$ real matrices such that

$\displaystyle \text{rank}(AB-BA+I) = 1,$

where ${I}$ is the ${n\times n}$ identity matrix. Prove that

$\displaystyle \text{tr}(ABAB)-\text{tr}(A^2B^2) = \frac{1}{2}n(n-1).$

(proposed by Rustam Turdibaev, V.I. Romanovskiy Institute of Mathematics)

Hint: Every time you hear about a rank 1 matrix you should think of “column matrix times line matrix”. Indeed, writing $AB-BA+I = cd^T$ with $c,d$ column vectors, gives $AB-BA = cd^T-I$ . Moreover, taking trace in the above equality and using the fact that you can perform circular permutations in products in traces, you obtain that $tr(cd^T) = d^Tc = n$ .

Moreover, squaring $AB-BA = cd^T-I$ gives

$\displaystyle ABAB+BABA-ABBA-BAAB = d^Tc(cd^T) - 2d^Tc+I$

Taking trace above gives the desired result!

Categories: Algebra, Combinatorics, Higher Algebra, IMO, Linear Algebra, Olympiad, Problem Solving Tags: Combinatorics, IMC, linear algebra, Problem Solving

IMC 2016 – Day 1 – Problem 2

July 27, 2016 beni22sof Leave a comment

Problem 2. Let ${k}$ and ${n}$ be positive integers. A sequence ${(A_1,...,A_k)}$ of ${n\times n}$ matrices is preferred by Ivan the Confessor if ${A_i^2 \neq 0}$ for ${1\leq i \leq k}$ , but ${A_iA_j = 0}$ for ${1\leq i,j \leq k}$ with ${i \neq j}$ . Show that if ${k \leq n}$ in al preferred sequences and give an example of a preferred sequence with ${k=n}$ for each ${n}$ .

Categories: Algebra, Uncategorized Tags: Algebra, IMC, linear algebra, matrix

SEEMOUS 2016 – Problems

March 5, 2016 beni22sof 3 comments

Problem 1. Let ${f}$ be a continuous and decreasing real valued function defined on ${[0,\pi/2]}$ . Prove that

$\displaystyle \int_{\pi/2-1}^{\pi/2} f(x)dx \leq \int_0^{\pi/2} f(x)\cos x dx \leq \int_0^1 f(x) dx.$

When do we have equality?

Problem 2. a) Prove that for every matrix ${X \in \mathcal{M}_2(\Bbb{C})}$ there exists a matrix ${Y \in \mathcal{M}_2(\Bbb{C})}$ such that ${Y^3 = X^2}$ .

b) Prove that there exists a matrix ${A \in \mathcal{M}_3(\Bbb{C})}$ such that ${Z^3 \neq A^2}$ for all ${Z \in \mathcal{M}_3(\Bbb{C})}$ .

Problem 3. Let ${A_1,A_2,...,A_k}$ be idempotent matrices ( ${A_i^2 = A_i}$ ) in ${\mathcal{M}_n(\Bbb{R})}$ . Prove that

$\displaystyle \sum_{i=1}^k N(A_i) \geq \text{rank} \left(I-\prod_{i=1}^k A_i\right),$

where ${N(A_i) = n-\text{rank}(A_i)}$ and ${\mathcal{M}_n(\Bbb{R})}$ is the set of ${n \times n}$ matrices with real entries.

Problem 4. Let ${n \geq 1}$ be an integer and set

$\displaystyle I_n = \int_0^\infty \frac{\arctan x}{(1+x^2)^n}dx.$

Prove that

a) $\sum_{i=1}^\infty \frac{I_n}{n} =\frac{\pi^2}{6}.$

b) $\int_0^\infty \arctan x \cdot \ln \left( 1+\frac{1}{x^2}\right) dx = \frac{\pi^2}{6}$ .

Some hints follow.

Categories: Algebra, Analysis, Linear Algebra, Olympiad, Uncategorized Tags: Algebra, Analysis, linear algebra, SEEMOUS

Vojtech Jarnik Competition 2015 – Problems Category 2

March 27, 2015 beni22sof Leave a comment

Problem 1. Let ${A}$ and ${B}$ be two ${3 \times 3}$ matrices with real entries. Prove that

$\displaystyle A - (A^{-1}+(B^{-1}-A)^{-1})^{-1} = ABA,$

provided all the inverses appearing on the left-hand side of the equality exist.

Problem 2. Determine all pairs ${(n,m)}$ of positive integers satisfying the equation

$\displaystyle 5^n = 6m^2+1.$

Problem 3. Determine the set of real values ${x}$ for which the following series converges, and find its sum:

$\displaystyle \sum_{n=1}^\infty \left( \sum_{k_i \geq 0, k_1+2k_2+...+nk_n = n} \frac{(k_1+...+k_n)!}{k_1!...k_n!} x^{k_1+...+k_n}\right).$

Problem 4. Find all continuously differentiable functions ${f : \Bbb{R} \rightarrow \Bbb{R}}$ , such that for every ${a \geq 0}$ the following relation holds:

$\displaystyle \int_{D(a)} xf\left( \frac{ay}{\sqrt{x^2+y^2}}\right) dxdydz = \frac{\pi a^3}{8}(f(a)+\sin a -1),$

where ${D(a) = \left\{ (x,y,z) : x^2+y^2+z^2 \leq a^2,\ |y| \leq \frac{x}{\sqrt{3}}\right\}}$

Categories: Olympiad Tags: Algebra, Analysis, linear algebra, matrix, series

Agregation 2014 – Mathematiques Generales – Parts 4-6

March 21, 2014 beni22sof Leave a comment

This is the second part of the Mathematiques Generales French Agregation written exam 2014. For the complete notation list and the first three parts look at this post.

Part 4 – Reduced form of permutations

For ${n \geq 2}$ we denote ${\Gamma}$ the set of pairs ${(i,j)}$ such that ${1\leq i<j \leq n}$ . We call the set of inversions of a permutation ${\sigma \in S_n}$ the set

$\displaystyle I(\sigma) = \{(i,j) \in \Gamma : \sigma(i)>\sigma(j)\}$

and we denote ${N(\sigma)}$ the cardinal of ${I(\sigma)}$ .

1. For which permutations ${\sigma \in S_n}$ is the number ${N(\sigma)}$ maximum?

For ${k \in [1..n-1]}$ we denote ${\tau_k \in S_k}$ the transposition which changes ${k}$ and ${k+1}$ .

4.2 (a) Let ${(k,\sigma) \in [1..n-1]\times S_n}$ . Prove that

$\displaystyle N(\tau_k \circ \sigma) = \begin{cases} N(\sigma)+1 & \text{ if }\sigma^{-1}(k) < \sigma^{-1}(k+1)\\ N(\sigma)-1 & \text{ if }\sigma^{-1}(k) > \sigma^{-1}(k+1), \end{cases}$

and that ${I(\tau_k \circ \sigma)}$ is obtained from ${I(\sigma)}$ by adding or removing an element of ${\Gamma}$ .

(b) Find explicitly ${\sigma^{-1} \circ \tau_k \circ \sigma}$ in function of the element of ${I(\tau_k \circ \sigma)}$ which makes it differ from ${I(\sigma)}$ .

Let ${T= \{ \tau_1,...,\tau_{n-1} \}}$ . We call word a finite sequence ${m=(t_1,...,t_l)}$ of elements of ${T}$ . We say that ${l}$ is the length of ${m}$ and that the elements ${t_1,..,t_l}$ are the letters of ${m}$ . The case of a void word ${(l=0)}$ is authorized.

A writing of a permutation ${\sigma \in S_n}$ is a word ${m=(t_1,...,t_l)}$ such that ${\sigma =(t_1,...,t_l)}$ . We make the convention that the permutation which corresponds to the void word is the identity.

Categories: Algebra, Linear Algebra Tags: agregation, linear algebra, matrix, permutation

Agregation 2014 – Mathematiques Generales – Parts 1-3

March 20, 2014 beni22sof 1 comment

This post contains the first three parts of the the Mathematiques Generales part French Agregation contest 2014.

Introduction and notations

For ${m \leq n}$ we denote ${ [m..n] =\{m,m+1,..,n\} }$ . For an integer ${n \geq 1}$ we denote ${S_n}$ the group of permutations of ${[1..n]}$ .

We say that a square matrix is inferior (superior) unitriangular if it is inferior (superior) triangular and all its diagonal elements are equal to ${1}$ .

For two integers ${ n \geq 1}$ and ${k \geq 0}$ we denote ${\mathcal{P}_k(n)}$ the family of ${k}$ -element subsets of ${[1..n]}$ .

Let ${m,n}$ be two positive integers and ${A}$ a ${m\times n}$ matrix with elements in a field ${\Bbb{K}}$ . (all fields are assumed commutative in the sequel) A minor of ${A}$ is the determinant of a square matrix extracted from ${A}$ . We can define for ${k \in [1..\min(m,n)]}$ and ${(I,J) \in \mathcal{P}_k(m) \times \mathcal{P}_k(n)}$ the minor

$\displaystyle \left| \begin{matrix}a_{i_1,j_1} & ... & a_{i_1,j_k} \\ \vdots & \ddots & \vdots \\ a_{i_k,j_1} & ... & a_{i_k,j_k} \end{matrix} \right|$

where ${i_1,..,i_k}$ (respectively ${j_1,..,j_k}$ ) are the elements of ${I}$ (respectively ${J}$ ) arranged in increasing order. We denote this minor ${\Delta_{I,J}(A)}$ .

Categories: Analysis, Group Theory, Higher Algebra, Linear Algebra Tags: agregation, linear algebra, matrix

Sierpinski’s Theorem for Additive Functions

January 26, 2014 beni22sof 1 comment

We say that ${f: \Bbb{R} \rightarrow \Bbb{R}}$ is an additive function if

$\displaystyle f(x+y)=f(x)+f(y),\ \forall x,y \in \Bbb{R}.$

1. Prove that there exist additive functions which are discontinuous with or without the Darboux Property.

2. Prove that for every additive function ${f}$ there exist two functions ${f_1,f_2:\Bbb{R} \rightarrow \Bbb{R}}$ which are additive, have the Darboux Property, and ${f=f_1+f_2}$ .

The second part is similar to Sierpinski’s Theorem which states that every real function can be written as the sum of two real functions with Darboux property.

(A function ${g:I \rightarrow \Bbb{R}}$ has the Darboux property if for every ${[a,b]\subset I}$ , ${g([a,b])}$ is an interval.)

Categories: Analysis, Linear Algebra, Topology Tags: additive functions, Analysis, darboux, linear algebra, sierpinski

Beni Bogoşel's blog

Archive

IMC 2020 Day 1 – Some Hints for Problems 1-2

IMC 2016 – Day 1 – Problem 2

SEEMOUS 2016 – Problems

Vojtech Jarnik Competition 2015 – Problems Category 2

Agregation 2014 – Mathematiques Generales – Parts 4-6

Agregation 2014 – Mathematiques Generales – Parts 1-3

Sierpinski’s Theorem for Additive Functions

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll

Archive

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll