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

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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}<b^{k-1}+b^{k-2}+\cdots+k+1<b^{k-1}+\binom{k-1}{k-2}b^{k-2}+\cdots+\binom{k-1}1b+1=(b+1)^{k-1}.$$

Answer 4

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.