MathDB
Problems
Contests
Undergraduate contests
Brazil Undergrad MO
2022 Brazil Undergrad MO
2
2
Part of
2022 Brazil Undergrad MO
Problems
(1)
Two matrices that generate a whole family
Source: Brazilian Undergrad Mathematics Olympiad 2022 P2
11/23/2022
Let
G
G
G
be the set of
2
×
2
2\times 2
2
×
2
matrices that such
G
=
{
(
a
b
c
d
)
∣
a
,
b
,
c
,
d
∈
Z
,
a
d
−
b
c
=
1
,
c
is a multiple of
3
}
G = \left\{ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \mid\, a,b,c,d \in \mathbb{Z}, ad-bc = 1, c \text{ is a multiple of } 3 \right\}
G
=
{
(
a
c
b
d
)
∣
a
,
b
,
c
,
d
∈
Z
,
a
d
−
b
c
=
1
,
c
is a multiple of
3
}
and two matrices in
G
G
G
:
A
=
(
1
1
0
1
)
B
=
(
−
1
1
−
3
2
)
A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\;\;\; B = \begin{pmatrix} -1 & 1 \\ -3 & 2 \end{pmatrix}
A
=
(
1
0
1
1
)
B
=
(
−
1
−
3
1
2
)
Show that any matrix in
G
G
G
can be written as a product
M
1
M
2
⋯
M
r
M_1M_2\cdots M_r
M
1
M
2
⋯
M
r
such that
M
i
∈
{
A
,
A
−
1
,
B
,
B
−
1
}
,
∀
i
≤
r
M_i \in \{A, A^{-1}, B, B^{-1}\}, \forall i \leq r
M
i
∈
{
A
,
A
−
1
,
B
,
B
−
1
}
,
∀
i
≤
r
linear algebra
matrix