# Find matrix $A\in \mathcal{M}_n (\mathbb{N})$ such that $A^k =\left( \sum_{i=1}^{k}10^{i-1} \right)A$.

I was watching this video by Flammable Maths about why $$\begin{pmatrix} 3 &4\\ 6&8 \end{pmatrix}^2 = \begin{pmatrix} 33 &44\\ 66&88 \end{pmatrix}$$ In the video, it is left as a challenge for the viewer to see if you can generalize the result as follows:

Given some $$k \in \mathbb{N}\cap[2,\infty),$$ can you find a matrix $$A\in \mathcal{M}_{n \times n} (\mathbb{N})$$ such that $$A^k =\left( \sum_{i=1}^{k}10^{i-1} \right)A$$?

I attempted a solution to this problem and did the following. I supposed (with the intention of hopefully simplifying calculations) that $$A$$ is diagonalizable. This means that I can write the equation we want as $$PD^{k} P^{-1}= \left( \sum_{i=1}^{k}10^{i-1} \right)PD P^{-1}$$ Now, taking the determinant on both sides I get that \begin{align*} &|P||D|^k|P^{-1}| = \left( \sum_{i=1}^{k}10^{i-1} \right)^n |P||D| |P^{-1}|\\ \implies & \left(\prod_{j=1}^n \lambda_j\right)^k = \left( \sum_{i=1}^{k}10^{i-1} \right)^n\left(\prod_{j=1}^n \lambda_j\right)\\ \implies & \prod_{j=1}^n \lambda_j^{k-1} = \left( \sum_{i=1}^{k}10^{i-1} \right)^n \end{align*} where the $$\lambda_j$$'s are the eigenvalues of $$A$$. From here I think that if I find a set of eigenvalues that satisfy the above equation I can reconstruct a matrix which satisfies our original intended equation, however, I'm not sure if this is a good way to approach this problem.

Does anyone know a better way to solve this? Or does anyone have any other ideas on how to tackle it? Ideally, I would like to find some patter or family of matrices which satisfy the desired property, buy any and all suggestions would be greatly appreciated. Thank you very much!

## Edit:

As pointed out by levap in the comments, it's impossible to find a solution of a matrix made up of strictly positive integers for $$k \ge 3$$. However, to not get rid of the possibility of other interesting solutions and/or observations, I'll clarify that other types of solutions with matrices in $$\mathcal{M}_n (\mathbb{Z})$$, $$\mathcal{M}_n (\mathbb{Q})$$ or even in $$\mathcal{M}_n (\mathbb{R})$$ will happily be considered for the bounty if you think they're similar to the original problem. In short, if you find something you think is interesting, even if it's not too similar to $$\begin{pmatrix} 3 &4\\ 6&8 \end{pmatrix}$$, please post them nevertheless. Thank you!

• Are you hoping for $A^k = (\sum_{i = 1}^{k}10^{i-1})A$ for all integers $k$, or for just some integers $k$? Sep 27, 2020 at 23:00
• All $k$ isn't possible since $A^2 = 11A$ implies $A^3 = 11A^2 = 121A$ which contradicts $A^3 = 111A$ unless $A = 0$. Hence, why I was asking for clarification on your question. Sep 27, 2020 at 23:10
• It might be worth noting that the $A$ given in the example isn't invertible ($\det(A)=3\cdot8-4\cdot6=0$), so working with the determinant may not be all that helpful. Sep 27, 2020 at 23:22
• @RobertLee: If you insist that the entries of $A$ are natural numbers (positive, non-zero) then there won't be a solution even for $k = 3$. The reason is that if $A^3 - 111A = A(A^2 - 111) = 0$, then the minimal polynomial of $A$ (over $\mathbb{Q}$) must divide $X(X^2 - 111)$. If the minimal polynomial is $X$ then $A = 0$. If the minimal polynomial is $X^2 - 111$ then the characteristic polynomial is $(X^2 - 111)^r$. If the minimal polynomial is $X(X^2 - 111)$ the characteristic polynomial will be $X^l (X^2 - 111)^r$. In any case, since the one-before-last coefficient of the Sep 30, 2020 at 13:20
• characteristic polynomial is zero, we must have $\operatorname{trace}(A) = 0$. This means that some of the diagonal entries of $A$ must be non-negative and some must be non-positive. The examples of Misha and TheSilverDoe are just the companion matrices of $X^{k-1} - \frac{10^k - 1}{10 - 1}$ so the satisfy the equation but unfortunately have many zeroes. If you want, you can trade the zeros for negative integers. However, I'm not sure you can take the integers to be single digit numbers (which is crucial for the "doubling dibits" property of the original matrix). Sep 30, 2020 at 13:20

There is a partial answer, which corresponds to the value $$k=2.$$

Firstly, since $$\det A^k= {\det}^k A = \underbrace{111\dots11}_k\det A,$$ then the easiest case of the solution is $$\det A=0,\tag1$$ as in the given example.

Let us consider the possible dimensions $$n$$ of the matrix $$A.$$

$$\color{brown}{\textbf{Case n=1.}}$$

The case is trivial, it does not correspond with the task statement.

Also, the equation $$a^k = \underbrace{111\cdot11}_k$$ has not solutions.

This fact excludes solutions in the form $$A=aE,$$ where $$\;E\;$$ is an arbitrary unit matrix (or transformed unit matrix).

$$\color{brown}{\textbf{Case n=2.}}$$

The equation $$\begin{pmatrix} a & b \\ c & d\end{pmatrix}^2 = 11\begin{pmatrix} a & b \\ c & d\end{pmatrix},$$ or $$\begin{pmatrix} a^2+bc & b(a+d) \\ c(a+d) & bc+d^2\end{pmatrix}^2 = \begin{pmatrix} 11a & 11b \\ 11c & 11d\end{pmatrix},$$ $$\begin{cases} a+d=11\\ bc = ad, \end{cases}$$

leads to the solutions in the matrix forms of $$\begin{cases} \begin{pmatrix} 2 & 9 \\ 2 & 9\end{pmatrix}, \begin{pmatrix} 2 & 2 \\ 9 & 9\end{pmatrix}, \begin{pmatrix} 2 & 3 \\ 6 & 9\end{pmatrix}, \begin{pmatrix} 2 & 6 \\ 3 & 9\end{pmatrix}; \\[4pt] \begin{pmatrix} 9 & 9 \\ 2 & 2\end{pmatrix}, \begin{pmatrix} 9 & 2 \\ 9 & 2\end{pmatrix}, \begin{pmatrix} 9 & 3 \\ 6 & 2\end{pmatrix}, \begin{pmatrix} 9 & 6 \\ 3 & 2\end{pmatrix}; \\[4pt] \begin{pmatrix} 3 & 8 \\ 3 & 8\end{pmatrix}, \begin{pmatrix} 3 & 3 \\ 8 & 8\end{pmatrix}, \begin{pmatrix} 3 & 4 \\ 6 & 8\end{pmatrix}, \begin{pmatrix} 3 & 6 \\ 4 & 8\end{pmatrix}; \\[4pt] \begin{pmatrix} 8 & 8 \\ 3 & 3\end{pmatrix}, \begin{pmatrix} 8 & 3 \\ 8 & 3\end{pmatrix}, \begin{pmatrix} 8 & 4 \\ 6 & 3\end{pmatrix}, \begin{pmatrix} 8 & 6 \\ 4 & 3\end{pmatrix}; \\[4pt] \begin{pmatrix} 4 & 7 \\ 4 & 7\end{pmatrix}, \begin{pmatrix} 4 & 4 \\ 7 & 7\end{pmatrix}, \begin{pmatrix} 7 & 7 \\ 4 & 4\end{pmatrix}, \begin{pmatrix} 7 & 4 \\ 7 & 4\end{pmatrix}; \\[4pt] \begin{pmatrix} 5 & 6 \\ 5 & 6\end{pmatrix}, \begin{pmatrix} 5 & 5 \\ 6 & 6\end{pmatrix}, \begin{pmatrix} 6 & 6 \\ 5 & 5\end{pmatrix}, \begin{pmatrix} 6 & 5 \\ 6 & 5\end{pmatrix}. \end{cases}\tag2$$

For example, $$\begin{pmatrix} 2 & 6 \\ 3 & 9\end{pmatrix}^2 = \begin{pmatrix} 22 & 66 \\ 33 & 99\end{pmatrix},$$

All the solutions satisfies to the next conditions:

• the sum of rows(columns) divides to 11;
• the rows(columns) are collinear.

$$\color{brown}{\textbf{Case n=3.}}$$

Let us search non-trivial solutions in the form of $$A = \begin{pmatrix} k & a & b \\ ky & ay & by \\ kz & az & bz \tag3\end{pmatrix},$$ then WLOG $$\begin{cases} bz = 11-k-ay\\[4pt] a \le y, \quad b\le z, \end{cases}$$ and this lead to the basic equalities in the forms of \begin{align} &\begin{pmatrix} 1 & 1 & 1 \\ y & y & y \\ 10-y & 10-y & 10-y\end{pmatrix}^2 = 11\,\begin{pmatrix} 1 & 1 & 1 \\ y & y & y \\ 10-y & 10-y & 10-y\end{pmatrix}, \qquad (y=1,2,\dots,9);\\[4pt] &\begin{pmatrix} 1 & 1 & 2 \\ 10-2z & 10-2z & 20-4z \\ z & z & 2z \end{pmatrix}^2 = 11\begin{pmatrix} 1 & 1 & 2 \\ 10-2z & 10-2z & 20-4z \\ z & z & 2z \end{pmatrix},\qquad (z=2,3,4);\\[4pt] &\begin{pmatrix} 1 & 1 & 3 \\ 1 & 1 & 3 \\ 3 & 3 & 9 \end{pmatrix}^2 = \begin{pmatrix} 11 & 11 & 33 \\ 11 & 11 & 33 \\ 33 & 33 & 99 \end{pmatrix};\\[4pt] &\begin{pmatrix} 1 & 2 & 1 \\ y & 2y & y \\ 10-2y & 20-4y & 10-2y\end{pmatrix} = 11\begin{pmatrix} 1 & 2 & 1 \\ y & 2y & y \\ 10-2y & 20-4y & 10-2y\end{pmatrix},\qquad (y=2,3,4);\\[4pt] &\begin{pmatrix} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 3 & 6 & 6\end{pmatrix}^2 = \begin{pmatrix} 11 & 22 & 33 \\ 22 & 44 & 44 \\ 33 & 66 & 66\end{pmatrix};\\[4pt] &\begin{pmatrix} 1 & 2 & 2 \\ 3 & 6 & 6 \\ 2 & 4 & 4 \end{pmatrix}^2 = \begin{pmatrix} 11 & 22 & 22 \\ 33 & 66 & 66 \\ 22 & 44 & 44\end{pmatrix};\\[4pt] &\color{brown}{\mathbf{\begin{pmatrix} 1 & 3 & 1 \\ 3 & 9 & 3 \\ 1 & 3 & 1\end{pmatrix}^2 = \begin{pmatrix} 11 & 33 & 11 \\ 33 & 99 & 33 \\ 11 & 33 & 11\end{pmatrix};}}\\[4pt] &\begin{pmatrix} 2 & a & 9-a \\ 2 & a & 9-a \\ 2 & a & 9-a\end{pmatrix}^2 = 11 \begin{pmatrix} 2 & a & 9-a \\ 2 & a & 9-a \\ 2 & a & 9-a\end{pmatrix}, \qquad (a=1,2,\dots,8);\\[4pt] &\begin{pmatrix} 3 & a & 8-a \\ 3 & a & 8-a \\ 3 & a & 8-a\end{pmatrix}^2 = 11 \begin{pmatrix} 3 & a & 8-a \\ 3 & a & 8-a \\ 3 & a & 8-a\end{pmatrix}, \qquad (a=1,2,3,4);\\[4pt] &\begin{pmatrix} 1 & 2 & 8 \\ 1 & 2 & 8\\ 1 & 2 & 8\end{pmatrix}^2 = \begin{pmatrix} 11 & 22 & 88 \\ 11 & 22 & 88 \\ 11 & 22 & 88\end{pmatrix};\\[4pt] &\begin{pmatrix} 1 & 3 & 7 \\ 1 & 3 & 9 \\ 1 & 1 & 9\end{pmatrix}^2 = \begin{pmatrix} 11 & 33 & 77 \\ 11 & 33 & 77 \\ 11 & 33 & 77\end{pmatrix};\\[4pt] \end{align} etc.

Besides, $$\begin{pmatrix} 0 & 0 & 0 \\ 3 & 3 & 6 \\ 4 & 4 & 8\end{pmatrix}^2 = \begin{pmatrix} 0 & 0 & 0 \\ 33 & 33 & 66 \\ 44 & 44 & 88\end{pmatrix},$$ $$\color{brown}{{ \begin{pmatrix} 4 & 3 & 2 \\ 4 & 3 & 2 \\ 8 & 6 & 4 \end{pmatrix}^2 = \begin{pmatrix} 44 & 33 & 22 \\ 44 & 33 & 22 \\ 88 & 66 & 44 \end{pmatrix}. }}\tag4$$ At the same time, $$\color{brown}{{ \begin{pmatrix} 2 & 3 & 4 \\ 2 & 3 & 4 \\ 4 & 6 & 8 \end{pmatrix}^2 = 13_{\text{dec}} \begin{pmatrix} 2 & 3 & 4 \\ 2 & 3 & 4 \\ 4 & 6 & 8 \end{pmatrix} = \begin{pmatrix} 22 & 33 & 44 \\ 22 & 33 & 44 \\ 44 & 66 & 88 \end{pmatrix}_{12} }}\tag5$$ in twelve-digit number system.

Besides, this kind of matrices can be obtained, using transformations of the solutions.

$$\color{brown}{\mathbf{Case\ n\ge 4.}}$$

Solutions in the form of $$\begin{pmatrix} k & a & b & c & \dots \\ kz & az & bz & cz & \dots \\ ky & ay & by & cy & \dots \\ kx & ax & bx & cx & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}$$ can be obtained from the solutions of the equation $$k + az + by + cx + \dots = 11.$$

So there are a lot of solutions with a strictly positive elements. For example, $$\color{brown}{\mathbf{ \begin{pmatrix} 1&2&1&2&1 \\ 2&4&2&4&2 \\ 1&2&1&2&1 \\ 2&4&2&4&2 \\ 1&2&1&2&1 \end{pmatrix}^2 =\begin{pmatrix} 11&22&11&22&11 \\ 22&44&22&44&22 \\ 11&22&11&22&11 \\ 22&44&22&44&22 \\ 11&22&11&22&11 \end{pmatrix}.}}\tag6$$ Looks perfect the solution for $$n=11:$$ $$\color{brown}{\mathbf{ \begin{pmatrix} 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \\ 1&1&1&1&1& 1 &1&1&1&1&1 \end{pmatrix}.}}\tag7$$

If $$n>11,$$ then solutions should contain zeros.

$$\color{brown}{\textbf{Allowed transformations of matrices.}}$$

Allowed transformations of matrices are transposition and sparsing.

There are two kinds of the allowed sparsing:

• Inserting of the zero row and zero before or after diagonal element of matrix;
• Substitution of each matrices element $$a$$ to the $$2\times2$$ matrix in the form of $$\begin{pmatrix} a & 0 \\ 0& a \end{pmatrix}\tag8.$$

In particular, the matrices in the forms of $$\begin{pmatrix} 0 & 0 & 0 \\ 0 & a & b \\ 0 & c & d \end{pmatrix}, \begin{pmatrix} a & 0 & b \\ 0 & 0 & 0 \\ c & 0 & d \end{pmatrix}, \begin{pmatrix} a & b & 0 \\ c & d & 0 \\ 0 & 0 & 0 \end{pmatrix}, \tag9$$ where $$a,b,c,d$$ correspond to the $$2\times2$$ solutions $$(2),$$ are the solutions in the $$3\times3$$ case.

• good approach, and trace and determinant remain constant under similarity transform (+1) Oct 5, 2020 at 18:08
• Nov 10, 2020 at 19:43
• @GCab Once more interesting integral Feb 10, 2021 at 12:49

Here's a solution for all $$k$$: take a $$(k-1) \times (k-1)$$ matrix $$A$$ with $$A_{k-1,1} = \underbrace{11\dots1}_k$$, $$A_{i,i+1} = 1$$ for $$i=1,\dots,k-2$$, and all other entries $$0$$. For example, for $$k=6$$, take the following $$5 \times 5$$ matrix: $$\begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 111111 & 0 & 0 & 0 & 0 \end{bmatrix}$$ This works because $$A$$ satisfies $$A \vec{e}_i = \vec e_{i-1}$$ for $$i=2,\dots,k-1$$, and $$A \vec e_1 = \underbrace{11\dots1}_k \vec e_{k-1}$$. Therefore, for any $$i$$, $$A^{k-1} \vec e_i = \underbrace{11\dots1}_k \vec e_i$$, so $$A^{k-1} = \underbrace{11\dots1}_kI$$, and $$A^k = \underbrace{11\dots1}_kA$$.

The matrix $$A = \begin{pmatrix} 0 & 0 &\cdots & 0 & 0\\ 1 & 0 & \cdots & 0 & \sum_{i=1}^{k}10^{i-1}\\ 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix} \in \mathcal{M}_k(\mathbb{R})$$

satisfies $$A^k = \left(\sum_{i=1}^{k}10^{i-1}\right)A$$

The matrix you've given is rank $$1$$ and can be written as $$\begin{pmatrix}1\\2\end{pmatrix}\begin{pmatrix}3&4\end{pmatrix}.$$ So, to generalize this, you're looking for two (column) $$n$$-vectors $$v$$ and $$w$$ for which $$(vw^\intercal)^k=\left(\frac{10^k-1}9\right)vw^\intercal.$$ You can write $$(vw^\intercal)^k=v(w^\intercal v)^{k-1}w^\intercal=v(v\cdot w)^{k-1}w^\intercal,$$ so what you'd be looking for is any two vectors $$v,w$$ for which $$(v\cdot w)^{k-1}=\frac{10^k-1}9.$$ As noted in the comments, $$v$$ and $$w$$ can't be integral since $$\frac{10^k-1}9$$ is not a perfect $$k-1$$-th power for any $$k>2$$. However, if you pick any two vectors with dot product $$\sqrt[k-1]{\frac{10^k-1}9}$$ you'll get a working solution that has the same row/column scaling property as the given matrix.

As a side-note: You can't even make the vectors integral if you switch the base. To do so would require $$a^{k-1}=\frac{b^k-1}{b-1}$$ for some integers $$a,b$$ with $$k>2$$, but $$b^{k-1}