Matrices and combinatorics

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Matrices and combinatorics

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Ecuador National Olympiad OMEC level U 2024 P1 Day 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

147 posts

KAME06

#1 h Apr 5, 2025, 7:59 PM • 1 Y

Y by PikaPika999

Let $n \in \mathbb{Z}$ . A matrix is n-national if its size is $2 \times 2$ and their entries belong to the set $\{2, 2^2, 2^3, ..., 2^n\}$ . For example:
$\begin{bmatrix} 2 & 8 \\ 16 & 4 \end{bmatrix}, \begin{bmatrix} 4 & 4 \\ 8 & 8 \end{bmatrix}, \begin{bmatrix} 8 & 2 \\ 16 & 8 \end{bmatrix}$ For all $n \in \mathbb{Z}$ , find the number of invertible n-national matrices.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#2 h Apr 6, 2025, 2:15 PM

Y by

The entries from such are matrix are supposed to be in the set $\{2, 2^2, 2^3, ..., 2^n\}$ . This set appears to be empty for $n=0$ , so there are no 0-national matrices, let alone invertible ones.

Let $n \neq 0$ now. The matrices to be counted are of the form
$\begin{bmatrix} 2^a & 2^b \\ 2^c & 2^d \end{bmatrix} \quad \text{such that} \quad 2^a \cdot 2^d - 2^b \cdot 2^c \neq 0,$ where the inequality is equivalent to the matrix being invertible. The inequality is equivalent to $a+d \neq b+c$ . If we ignore the inequality for a moment, we have $n^4$ possible matrices. We must subtract those with $a+d=b+c$ . Here it becomes obvious that it does not matter if $a,b,c,d$ are in the range from $1$ to $n$ for a positive $n$ or in the range from $-1$ to $n$ for a negative $n$ . Let $n$ therefore be positive.

On both sides of the equation $a+d=b+c$ , the possible sums range from $2$ to $2n$ . For the sum 2, there is one choice for $a,d$ to produce that sum. For 3, there are two choices. We reach the maximum number of choices for the sum $n+1$ where we have $n$ choices. From then onward, we incrementally go down to one choice for the sum $2n$ .

As we need to produce the same sum with $a+d$ and $b+c$ , we must square each number of choices to obtain the number of combined choices for both sides of $a+d = b+c$ . Therefore, the total number of choices with $a + d = b + c$ is
$1^2 + 2^2 + 3^2 + \ldots (n-1)^2 + n^2 + (n-1)^2 + \ldots + 3^2 + 2^2 + 1^2 = n^2 + 2 \cdot \sum_{i=1}^{n-1} i^2 = n^2 + 2 \cdot \tfrac{1}{6} (n-1) \cdot n \cdot (2n-1) = \tfrac{2}{3} n^3 + \tfrac{1}{3} n.$ Therefore, for a positive $n$ , the number of invertible n-national matrices is
$n^4 - \tfrac{2}{3} n^3 - \tfrac{1}{3} n.$ For a negative $n$ , the variable $n$ needs to be replaced by $-n$ here.

This post has been edited 1 time. Last edited by Rainbow1971, Apr 6, 2025, 2:26 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a