Olympiad problems

2011 Putnam, A4

Tags: linear algebra , matrix , modular arithmetic , vector , polynomial , putnam matrices

For which positive integers $n$ is there an $n\times n$ matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

1973 IMO Longlists, 6

Tags: geometry , analytic geometry , linear algebra , matrix , pigeonhole principle , combinatorics

Let $P_i (x_i, y_i)$ (with $i = 1, 2, 3, 4, 5$) be five points with integer coordinates, no three collinear. Show that among all triangles with vertices at these points, at least three have integer areas.

2000 Iran MO (2nd round), 3

Tags: linear algebra , matrix , combinatorics

Let $M=\{1,2,3,\ldots, 10000\}.$ Prove that there are $16$ subsets of $M$ such that for every $a \in M,$ there exist $8$ of those subsets that intersection of the sets is exactly $\{a\}.$

1993 Greece National Olympiad, 4

Tags: symmetry , algebra , polynomial , linear algebra , matrix , inequalities

How many ordered four-tuples of integers $(a,b,c,d)$ with $0 < a < b < c < d < 500$ satisfy $a + d = b + c$ and $bc - ad = 93$?

2016 Korea USCM, 8

Tags: linear algebra , nilpotent , matrix , commutator

For a $n\times n$ complex valued matrix $A$, show that the following two conditions are equivalent. (i) There exists a $n\times n$ complex valued matrix $B$ such that $AB-BA=A$. (ii) There exists a positive integer $k$ such that $A^k = O$. ($O$ is the zero matrix.)

MIPT Undergraduate Contest 2019, 1.3

Tags: linear algebra , matrix

Given a natural number $n$, for what maximal value $k$ it is possible to construct a matrix of size $k \times n$ consisting only of elements $\pm 1$ in such a way that for any interchange of a $+1$ with a $-1$ or vice versa, its rank is equal to $k$?

2004 Polish MO Finals, 4

Tags: linear algebra , matrix , inequalities

Let real numbers $ a,b,c$. Prove that $ \sqrt{2(a^2\plus{}b^2)}\plus{}\sqrt{2(b^2\plus{}c^2)}\plus{}\sqrt{2(c^2\plus{}a^2)}\ge \sqrt{3(a\plus{}b)^2\plus{}3(b\plus{}c)^2\plus{}3(c\plus{}a)^2}$.

2012 Tuymaada Olympiad, 3

Tags: induction , linear algebra , matrix , combinatorics

Prove that $N^2$ arbitrary distinct positive integers ($N>10$) can be arranged in a $N\times N$ table, so that all $2N$ sums in rows and columns are distinct. [i]Proposed by S. Volchenkov[/i]

2006 IMC, 3

Tags: linear algebra , matrix , ring theory

Let $A$ be an $n$x$n$ matrix with integer entries and $b_{1},b_{2},...,b_{k}$ be integers satisfying $detA=b_{1}\cdot b_{2}\cdot ...\cdot b_{k}$. Prove that there exist $n$x$n$-matrices $B_{1},B_{2},...,B_{k}$ with integers entries such that $A=B_{1}\cdot B_{2}\cdot ...\cdot B_{k}$ and $detB_{i}=b_{i}$ for all $i=1,...,k$.

2015 Romania National Olympiad, 2

Tags: linear algebra , matrix

Let be a $ 5\times 5 $ complex matrix $ A $ whose trace is $ 0, $ and such that $ I_5-A $ is invertible. Prove that $ A^5\neq I_5. $

2003 IMO Shortlist, 4

Tags: linear algebra , matrix , combinatorics

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

1997 AMC 12/AHSME, 8

Tags: linear algebra , matrix

Mientka Publishing Company prices its bestseller [i]Where's Walter?[/i] as follows: \[C(n) \equal{} \begin{cases} 12n, &\text{if } 1 \le n \le 24\\ 11n, &\text{if } 25 \le n \le 48\\ 10n, &\text{if } 49 \le n \end{cases}\] where $ n$ is the number of books ordered, and $ C(n)$ is the cost in dollars of $ n$ books. Notice that $ 25$ books cost less than $ 24$ books. For how many values of $ n$ is it cheaper to buy more than $ n$ books than to buy exactly $ n$ books? $ \textbf{(A)}\ 3\qquad \textbf{(B)}\ 4\qquad \textbf{(C)}\ 5\qquad \textbf{(D)}\ 6\qquad \textbf{(E)}\ 8$

1992 Putnam, B6

Tags: linear algebra , matrix

Let $M$ be a set of real $n \times n$ matrices such that i) $I_{n} \in M$, where $I_n$ is the identity matrix. ii) If $A\in M$ and $B\in M$, then either $AB\in M$ or $-AB\in M$, but not both iii) If $A\in M$ and $B \in M$, then either $AB=BA$ or $AB=-BA$. iv) If $A\in M$ and $A \ne I_n$, there is at least one $B\in M$ such that $AB=-BA$. Prove that $M$ contains at most $n^2 $ matrices.

1989 Irish Math Olympiad, 2

Tags: matrix , combinatorics , magic square

A 3x3 magic square, with magic number $m$, is a $3\times 3$ matrix such that the entries on each row, each column and each diagonal sum to $m$. Show that if the square has positive integer entries, then $m$ is divisible by $3$, and each entry of the square is at most $2n-1$, where $m=3n$. An example of a magic square with $m=6$ is \[\left( \begin{array}{ccccc} 2 & 1 & 3\\ 3 & 2 & 1\\ 1 & 3 & 2 \end{array} \right)\]

2005 Olympic Revenge, 4

Tags: linear algebra , matrix , abstract algebra , induction

Let A be a symmetric matrix such that the sum of elements of any row is zero. Show that all elements in the main diagonal of cofator matrix of A are equal.

2012 VJIMC, Problem 2

Tags: matrix , linear algebra

Let $M$ be the (tridiagonal) $10\times10$ matrix $$M=\begin{pmatrix}-1&3&0&\cdots&\cdots&\cdots&0\\3&2&-1&0&&&\vdots\\0&-1&2&-1&\ddots&&\vdots\\\vdots&0&-1&2&\ddots&0&\vdots\\\vdots&&\ddots&\ddots&\ddots&-1&0\\\vdots&&&0&-1&2&-1\\0&\cdots&\cdots&\cdots&0&-1&2\end{pmatrix}$$Show that $M$ has exactly nine positive real eigenvalues (counted with multiplicities).

2003 Putnam, 1

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

Do there exist polynomials $a(x)$, $b(x)$, $c(y)$, $d(y)$ such that \[1 + xy + x^2y^2= a(x)c(y) + b(x)d(y)\] holds identically?

1977 Miklós Schweitzer, 5

Tags: linear algebra , matrix , superior algebra

Suppose that the automorphism group of the finite undirected graph $ X\equal{}(P, E)$ is isomorphic to the quaternion group (of order $ 8$). Prove that the adjacency matrix of $ X$ has an eigenvalue of multiplicity at least $ 4$. ($ P\equal{} \{ 1,2,\ldots, n \}$ is the set of vertices of the graph $ X$. The set of edges $ E$ is a subset of the set of all unordered pairs of elements of $ P$. The group of automorphisms of $ X$ consists of those permutations of $ P$ that map edges to edges. The adjacency matrix $ M\equal{}[m_{ij}]$ is the $ n \times n$ matrix defined by $ m_{ij}\equal{}1$ if $ \{ i,j \} \in E$ and $ m_{i,j}\equal{}0$ otherwise.) [i]L. Babai[/i]

2023 SEEMOUS, P1

Tags: linear algebra , matrix , determinant

Prove that if $A{}$ and $B{}$ are $n\times n$ matrices with complex entries which satisfy \[A=AB-BA+A^2B-2ABA+BA^2+A^2BA-ABA^2,\]then $\det(A)=0$.

2004 Purple Comet Problems, 24

Tags: linear algebra , matrix

The determinant \[\begin{vmatrix}3&-2&5\\ 7&1&-4\\ 5&2&3\end{vmatrix}\] has the same value as the determinant \[\begin{vmatrix}x&1+x&2+x\\ 3&0&1\\ 1&1&0\end{vmatrix}\] Find $x$.

1994 IMC, 4

Tags: linear algebra , matrix

Let $A$ be a $n\times n$ diagonal matrix with characteristic polynomial $$(x-c_1)^{d_1}(x-c_2)^{d_2}\ldots (x-c_k)^{d_k}$$ where $c_1, c_2, \ldots, c_k$ are distinct (which means that $c_1$ appears $d_1$ times on the diagonal, $c_2$ appears $d_2$ times on the diagonal, etc. and $d_1+d_2+\ldots + d_k=n$). Let $V$ be the space of all $n\times n$ matrices $B$ such that $AB=BA$. Prove that the dimension of $V$ is $$d_1^2+d_2^2+\cdots + d_k^2$$

2005 Germany Team Selection Test, 3

Tags: linear algebra , matrix , combinatorics , extremal combinatorics

For an ${n\times n}$ matrix $A$, let $X_{i}$ be the set of entries in row $i$, and $Y_{j}$ the set of entries in column $j$, ${1\leq i,j\leq n}$. We say that $A$ is [i]golden[/i] if ${X_{1},\dots ,X_{n},Y_{1},\dots ,Y_{n}}$ are distinct sets. Find the least integer $n$ such that there exists a ${2004\times 2004}$ golden matrix with entries in the set ${\{1,2,\dots ,n\}}$.

2024 CIIM, 2

Tags: linear algebra , matrix , determinant , symmetric matrix

Let $n$ be a positive integer, and let $M_n$ be the set of invertible matrices with integer entries and size $n \times n$. (a) Find the largest possible value of $n$ such that there exists a symmetric matrix $A \in M_n$ satisfying \[ \det(A^{20} + A^{24}) < 2024. \] (b) Prove that for every $n$, there exists a matrix $B \in M_n$ such that \[ \det(B^{20} + B^{24}) < 2024. \]

2017 India IMO Training Camp, 3

Tags: linear algebra , matrix , combinatorics

Let $n \ge 1$ be a positive integer. An $n \times n$ matrix is called [i]good[/i] if each entry is a non-negative integer, the sum of entries in each row and each column is equal. A [i]permutation[/i] matrix is an $n \times n$ matrix consisting of $n$ ones and $n(n-1)$ zeroes such that each row and each column has exactly one non-zero entry. Prove that any [i]good[/i] matrix is a sum of finitely many [i]permutation[/i] matrices.

2004 IMO Shortlist, 4

Tags: linear algebra , matrix , algebra , probability , combinatorics

Consider a matrix of size $n\times n$ whose entries are real numbers of absolute value not exceeding $1$. The sum of all entries of the matrix is $0$. Let $n$ be an even positive integer. Determine the least number $C$ such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding $C$ in absolute value. [i]Proposed by Marcin Kuczma, Poland[/i]