Olympiad problems

1986 Miklós Schweitzer, 2

Show that if $k\leq \frac n2$ and $\mathcal F$ is a family $k\times k$ submatrices of an $n\times n$ matrix such that any two intersect then $$|\mathcal F|\leq \binom{n-1}{k-1}^2$$ [Gy. Katona]

1990 Putnam, B3

Tags: pigeonhole principle , linear algebra , matrix

Let $S$ be a set of $ 2 \times 2 $ integer matrices whose entries $a_{ij}(1)$ are all squares of integers and, $(2)$ satisfy $a_{ij} \le 200$. Show that $S$ has more than $ 50387 (=15^4-15^2-15+2) $ elements, then it has two elements that commute.

1996 India National Olympiad, 6

Tags: combinatorics , linear algebra , matrix

There is a $2n \times 2n$ array (matrix) consisting of $0's$ and $1's$ and there are exactly $3n$ zeroes. Show that it is possible to remove all the zeroes by deleting some $n$ rows and some $n$ columns.

1971 IMO Shortlist, 13

Tags: matrix , linear algebra , combinatorics , algebra , combinatorial inequality

Let $ A \equal{} (a_{ij})$, where $ i,j \equal{} 1,2,\ldots,n$, be a square matrix with all $ a_{ij}$ non-negative integers. For each $ i,j$ such that $ a_{ij} \equal{} 0$, the sum of the elements in the $ i$th row and the $ j$th column is at least $ n$. Prove that the sum of all the elements in the matrix is at least $ \frac {n^2}{2}$.

2004 District Olympiad, 4

Tags: matrix , algebra , polynomial , calculus , derivative , linear algebra

Let $A=(a_{ij})\in \mathcal{M}_p(\mathbb{C})$ such that $a_{12}=a_{23}=\ldots=a_{p-1,p}=1$ and $a_{ij}=0$ for any other entry. a)Prove that $A^{p-1}\neq O_p$ and $A^p=O_p$. b)If $X\in \mathcal{M}_{p}(\mathbb{C})$ and $AX=XA$, prove that there exist $a_1,a_2,\ldots,a_p\in \mathbb{C}$ such that: \[X=\left( \begin{array}{ccccc} a_1 & a_2 & a_3 & \ldots & a_p \\ 0 & a_1 & a_2 & \ldots & a_{p-1} \\ 0 & 0 & a_1 & \ldots & a_{p-2} \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & \ldots & a_1 \end{array} \right)\] c)If there exist $B,C\in \mathcal{M}_p(\mathbb{C})$ such that $(I_p+A)^n=B^n+C^n,\ (\forall)n\in \mathbb{N}^*$, prove that $B=O_p$ or $C=O_p$.

2015 VTRMC, Problem 3

Tags: linear algebra , matrices

Let $(a_i)_{1\le i\le2015}$ be a sequence consisting of $2015$ integers, and let $(k_i)_{1\le i\le2015}$ be a sequence of $2015$ positive integers (positive integer excludes $0$). Let $$A=\begin{pmatrix}a_1^{k_1}&a_1^{k_2}&\cdots&a_1^{k_{2015}}\\a_2^{k_1}&a_2^{k_2}&\cdots&a_2^{k_{2015}}\\\vdots&\vdots&\ddots&\vdots\\a_{2015}^{k_1}&a_{2015}^{k_2}&\cdots&a_{2015}^{k_{2015}}\end{pmatrix}.$$Prove that $2015!$ divides $\det A$.

2017 Miklós Schweitzer, 2

Tags: matrix , linear algebra , abstract algebra , field

Prove that a field $K$ can be ordered if and only if every $A\in M_n(K)$ symmetric matrix can be diagonalized over the algebraic closure of $K$. (In other words, for all $n\in\mathbb{N}$ and all $A\in M_n(K)$, there exists an $S\in GL_n(\overline{K})$ for which $S^{-1}AS$ is diagonal.)

2019 LIMIT Category C, Problem 9

Tags: matrix , matrices , linear algebra

$P\in A_n(\mathbb R)=\{M_{n\times n}|M^2=M\}$. Which of the following are true? $\textbf{(A)}~P^T=P,\forall P\in A_n(\mathbb R)$ $\textbf{(B)}~\exists P\ne0,P\in A_n(\mathbb R)\text{ with }\operatorname{tr}(P)=0$ $\textbf{(C)}~\exists X_{n\times r}\text{ such that }Px=X\text{ for }r=\operatorname{rank}(P)$

1996 IMC, 9

Tags: linear algebra , group theory , abstract algebra

Let $G$ be the subgroup of $GL_{2}(\mathbb{R})$ generated by $A$ and $B$, where $$A=\begin{pmatrix} 2 &0\\ 0&1 \end{pmatrix},\; B=\begin{pmatrix} 1 &1\\ 0&1 \end{pmatrix}$$. Let $H$ consist of the matrices $\begin{pmatrix} a_{11} &a_{12}\\ a_{21}& a_{22} \end{pmatrix}$ in $G$ for which $a_{11}=a_{22}=1$. a) Show that $H$ is an abelian subgroup of $G$. b) Show that $H$ is not finitely generated.

2025 VJIMC, 2

Tags: rank , linear algebra , matrix

Let $A,B$ be two $n\times n$ complex matrices of the same rank, and let $k$ be a positive integer. Prove that $A^{k+1}B^k = A$ if and only if $B^{k+1}A^k = B$.

1990 Greece National Olympiad, 1

Tags: linear algebra , matrix

Let $A$ be a $2\,x\,2$ matrix with real numbers. Prove that if $A^3=\mathbb{O}$ then $A^2=\mathbb{O}$.

2011 Laurențiu Duican, 2

Tags: nilpotence , linear algebra

Let be a field $ \mathbb{F} $ and two nonzero nilpotent matrices $ M,N\in\mathcal{M}_2\left( \mathbb{F} \right) $ that commute. Show that: [b]a)[/b] $ MN=0 $ [b]b)[/b] there exists a nonzero element $ f\in\mathbb{F} $ such that $ M=fN $ [i]Dorel Miheț[/i]

2006 Iran MO (3rd Round), 1

Tags: matrix , linear algebra

Suppose that $A\in\mathcal M_{n}(\mathbb R)$ with $\text{Rank}(A)=k$. Prove that $A$ is sum of $k$ matrices $X_{1},\dots,X_{k}$ with $\text{Rank}(X_{i})=1$.

2004 Germany Team Selection Test, 2

Tags: combinatorics , linear algebra , matrix

Let $x_1,\ldots, x_n$ and $y_1,\ldots, y_n$ be real numbers. Let $A = (a_{ij})_{1\leq i,j\leq n}$ be the matrix with entries \[a_{ij} = \begin{cases}1,&\text{if }x_i + y_j\geq 0;\\0,&\text{if }x_i + y_j < 0.\end{cases}\] Suppose that $B$ is an $n\times n$ matrix with entries $0$, $1$ such that the sum of the elements in each row and each column of $B$ is equal to the corresponding sum for the matrix $A$. Prove that $A=B$.

2019 IMC, 2

Tags: linear algebra

A four-digit number $YEAR$ is called [i]very good[/i] if the system \begin{align*} Yx+Ey+Az+Rw& =Y\\ Rx+Yy+Ez+Aw & = E\\\ Ax+Ry+Yz+Ew & = A\\ Ex+Ay+Rz+Yw &= R \end{align*} of linear equations in the variables $x,y,z$ and $w$ has at least two solutions. Find all very good $YEAR$s in the 21st century. (The $21$st century starts in $2001$ and ends in $2100$.) [i]Proposed by Tomáš Bárta, Charles University, Prague[/i]

2008 District Olympiad, 2

Tags: matrix , linear algebra

Let $A,B\in \mathcal{M}_n(\mathbb{R})$. Prove that $\text{rank}\ A+\text{rank}\ B\le n$ if and only if there exists an invertible matrix $X\in \mathcal{M}_n(\mathbb{R})$ such that $AXB=O_n$.

2012 VJIMC, Problem 2

Tags: linear algebra , matrix

Determine all $2\times2$ integer matrices $A$ having the following properties: $1.$ the entries of $A$ are (positive) prime numbers, $2.$ there exists a $2\times2$ integer matrix $B$ such that $A=B^2$ and the determinant of $B$ is the square of a prime number.

2008 IMS, 1

Tags: linear algebra , matrix , induction , polynomial , algebra

Let $ A_1,A_2,\dots,A_n$ be idempotent matrices with real entries. Prove that: \[ \mbox{N}(A_1)\plus{}\mbox{N}(A_2)\plus{}\dots\plus{}\mbox{N}(A_n)\geq \mbox{rank}(I\minus{}A_1A_2\dots A_n)\] $ \mbox{N}(A)$ is $ \mbox{dim}(\mbox{ker(A)})$

2006 Miklós Schweitzer, 5

Tags: linear algebra

let $F_q$ be a finite field with char ≠ 2, and let $V = F_q \times F_q$ be the 2-dimensional vector space over $F_q$. Let L ⊂ V be a subset containing lines in all directions. The order of a point in V is the number of lines in L that pass through the point. Prove that L contains at least q lines having a third-order point.

2011 IMC, 2

Tags: matrix , linear algebra , function , polynomial , algebra

Does there exist a real $3\times 3$ matrix $A$ such that $\text{tr}(A)=0$ and $A^2+A^t=I?$ ($\text{tr}(A)$ denotes the trace of $A,\ A^t$ the transpose of $A,$ and $I$ is the identity matrix.) [i]Proposed by Moubinool Omarjee, Paris[/i]

2018 ISI Entrance Examination, 8

Tags: linear algebra

Let $n\geqslant 3$. Let $A=((a_{ij}))_{1\leqslant i,j\leqslant n}$ be an $n\times n$ matrix such that $a_{ij}\in\{-1,1\}$ for all $1\leqslant i,j\leqslant n$. Suppose that $$a_{k1}=1~~\text{for all}~1\leqslant k\leqslant n$$ and $~~\sum_{k=1}^n a_{ki}a_{kj}=0~~\text{for all}~i\neq j$. Show that $n$ is a multiple of $4$.

1980 VTRMC, 6

Tags: linear algebra

Given the linear fractional transformation of $x$ into $f_1(x) = \tfrac{2x-1}{x+1},$ define $f_{n+1}(x) = f_1(f_n(x))$ for $n=1,2,3,\ldots.$ It can be shown that $f_{35} = f_5.$ Determine $A,B,C,D$ so that $f_{28}(x) = \tfrac{Ax+B}{Cx+D}.$

2003 IMO Shortlist, 1

Tags: linear algebra , tetrahedron , geometry , algebra , 3d geometry , vector

Let $a_{ij}$ $i=1,2,3$; $j=1,2,3$ be real numbers such that $a_{ij}$ is positive for $i=j$ and negative for $i\neq j$. Prove the existence of positive real numbers $c_{1}$, $c_{2}$, $c_{3}$ such that the numbers \[a_{11}c_{1}+a_{12}c_{2}+a_{13}c_{3},\qquad a_{21}c_{1}+a_{22}c_{2}+a_{23}c_{3},\qquad a_{31}c_{1}+a_{32}c_{2}+a_{33}c_{3}\] are either all negative, all positive, or all zero. [i]Proposed by Kiran Kedlaya, USA[/i]

2009 AMC 12/AHSME, 9

Tags: geometry , analytic geometry , linear algebra , matrix , pythagorean theorem

Triangle $ ABC$ has vertices $ A\equal{}(3,0)$, $ B\equal{}(0,3)$, and $ C$, where $ C$ is on the line $ x\plus{}y\equal{}7$. What is the area of $ \triangle ABC$? $ \textbf{(A)}\ 6\qquad \textbf{(B)}\ 8\qquad \textbf{(C)}\ 10\qquad \textbf{(D)}\ 12\qquad \textbf{(E)}\ 14$

2009 Poland - Second Round, 3

Tags: algebra , vector , linear algebra

For every integer $n\ge 3$ find all sequences of real numbers $(x_1,x_2,\ldots ,x_n)$ such that $\sum_{i=1}^{n}x_i=n$ and $\sum_{i=1}^{n} (x_{i-1}-x_i+x_{i+1})^2=n$, where $x_0=x_n$ and $x_{n+1}=x_1$.