# Show that there exists a matrix with trace in the set $\{1,2,...,n\}.$

Let $$n$$ be a positive integer and let $$U$$ be a finite subset of $$M_{n\times n}(\mathbb{C})$$ which is closed under multiplication of matrices. Show that there exists a matrix $$A$$ in $$U$$ satisfying $$\text{trace}(A) \in \{1,...,n\}.$$

I was thinking if we look at this problem by contradiction. Then we have that for all matrices $$A$$ $$\text{trace}(A)>n$$ or $$\text{trace}(A)=0.$$ In the first case, we get that $$\det(A)<1$$ and the second case we get that $$\det{A}=0.$$ I am not sure how to proceed further, so any hint would be much appreciated.

• The $n\times n$ identity matrix has trace $n \in A$ Oct 18, 2018 at 16:51
• @amWhy Set $U$ is given, it's not as easy Oct 18, 2018 at 16:52
• @Jakobian In fact it is easy and the above comment gives an excellent hint: a non-empty finite subset of a group closed under the group's operation is in fact a subgroup. Oct 18, 2018 at 16:54
• @DonAntonio But it's not a group, it's a semigroup Oct 18, 2018 at 16:55
• I think the set $U=\{0_{n\times n}\}$ is a counter-example. Oct 18, 2018 at 17:02

Let $$A\in U$$. Since $$U$$ is finite, there exist $$a,b\in\mathbb N$$ such that $$A^a=A^b$$ and $$a < b$$. So the minimal polynomial of $$A$$ divides $$x^a-x^b$$. This shows that any eigen-value of $$A$$ is either $$0$$ or a root of unity.

Consider the matrices $$A^k$$ for $$k\in\mathbb N$$.

By this, the eigen-values of $$A^k$$ are the $$k$$-th powers of eigen-values of $$A$$, so we can find $$k$$ such that the eigen-values of $$A^k$$ are either $$0$$ or $$1$$. Then the trace of $$A^k$$ is a sum of $$n$$ numbers in $$\{0,1\}$$, so is an integer between $$0$$ and $$n$$.

Hope this helps.

A hint: Consider an element $$A$$. Since $$U$$ is closed under multiplication, for every natural number $$m$$, $$A^m \in U$$. However, $$U$$ is finite--so that means $$A^m$$ takes on finitely many values. What does that imply about $$A$$'s eigenvalues? The trace is the sum of its eigenvalues--must there be a $$m$$ such that $$\mathrm{Tr}(A^m)\in \mathbb N$$?

This is wrong unless the set contains zero

Pick any $$A \in U$$ and consider the sequence $$A,A^2,A^3,...$$. Since $$U$$ is finite, there must exist $$s such that $$A^s = A^t$$.

In particular, if $$\lambda$$ is an eigenvalue of $$A$$ we see that $$\lambda^s = \lambda^t$$ and hence either $$\lambda=0$$ or $$\lambda^{t-s} = 1$$. In other words, all eigenvalues of $$A^{t-s}$$ (which must be a member of $$U$$) satisfy $$\lambda^{t-s} \in \{0,1\}$$.

Consequently, $$\operatorname{tr} A^{t-s} \in \{0,...,n\}$$.