Let $A = [a_{ij}]_{1\le i,j\le d} \in M_d(\mathbb C)$ for fixed $d\in \mathbb N$. We denote the entries of $A^n$ by $$A^n = [a_{ij}^{(n)}]_{1\le i,j\le d}$$ for all $n\in \mathbb N$.
Claim: If $M > 0$ is such that $|a_{ij}|\le M$ for all $1\le i,j\le d$, then $$|a_{ij}^{(n)}|\le (dM)^n$$ for all $n\in \mathbb N$.
Proof. I have proved this claim by induction. The base case is trivial, since $d\ge 1$. It is easily seen that $$\left|a_{ij}^{(n+1)}\right| = \left|\sum_{p=1}^d a_{ip}^{(n)} a_{pj}\right| \le \sum_{p=1}^d |a_{ip}^{(n)}|| a_{pj}| \le \sum_{p=1}^d (dM)^n M = (dM)^{n+1}$$
Questions:
I am looking for direct proofs (i.e. without induction) of the above result. Could I get some suggestions?
Are better bounds known? That is, can we find $\lambda(M,n,d)$ such that if $|a_{ij}|\le M$ for all $1\le i,j\le d$, then $|a_{ij}^{(n)}|\le \lambda(M,n,d)$ for all $n\in \mathbb N$, where $\lambda(M,n,d) < (dM)^n$?
The best upper bound is $d^{n-1}M^n$: \begin{aligned} |(A^n)_{ij}| &=\left|\sum_{(k_1,k_2,\ldots,k_{n-1})\in[d]^{n-1}} a_{ik_1}a_{k_1k_2}\cdots a_{k_{n-1}j}\right|\\ &\le\sum_{(k_1,k_2,\ldots,k_{n-1})\in[d]^{n-1}} |a_{ik_1}a_{k_1k_2}\cdots a_{k_{n-1}j}|\\ &\le\sum_{(k_1,k_2,\ldots,k_{n-1})\in[d]^{n-1}}M^n\\ &=d^{n-1}M^n. \end{aligned} This bound is sharp. It is attained when every element of $A$ is equal to $M$.