# How to make this proof rigorous by introducing partition of numbers?

Question: Let $$n$$ be a positive integer and $$H_n=\{A=(a_{ij})_{n×n}\in M_n(K) : a_{ij}=a_{rs} \text{ whenever } i +j=r+s\}$$. Then what is $$\dim H_n$$?

Proof:

For $$n=2$$

$$H_2=\begin{pmatrix} a_{11}& a_{12}\\a_{12}&a_{22}\end{pmatrix}$$

Matrix of sum of indices $$J_n$$:

$$J_2=\begin{pmatrix}\color{red}{2} & \color{red}{3} \\{3}&\color{red}{4}\end{pmatrix}$$

$$\dim(H_2) =3=2\cdot 2-1$$

For $$n=3$$

$$H_3=\left(\begin{array}{cc|c} a_{11}& a_{12}&a_{13}\\ \hline a_{12}&a_{13}&a_{23}\\a_{13}&a_{23}&a_{33}\end{array}\right)$$

$$J_3=\begin{pmatrix}\color{red}{2} & \color{red}{3} &\color{red}{4}\\ 3 &4&\color{red}{5}\\4&{5}&\color{red}{6}\end{pmatrix}$$

$$\dim(H_3) =5=2\cdot 3-1$$

$$J_n=\left(\begin{array}{ccc|c} \color{red}{2}& \color{red}{3}&\color{red}{\ldots}&\color{red}{n+1}\\ \hline 3&4&\ldots&\color{red}{n+2}\\4&5&\ldots&\color{red}{n+3}\\\vdots&\vdots&\ldots&\color{red}{\vdots}\\n+1&n+2&\ldots&\color{red}{n+n}\end{array}\right)$$

$$\dim(H_n) =2n-1$$

$$\dim(H_n) = |\{2,3,\ldots,2n\}|=2n-1$$

How to make this proof rigorous by introducing partition of numbers?

From the work I have done so far, it is clear that I can find the basis and dimension. But I think the matrix of indices can simplify the problem easily. I need some nice tricks involving elementary number theory specially integer partitions on the matrix of indices.

• Taking $n=3$ as an example, I would try to prove that $$\begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{pmatrix}, \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 0\end{pmatrix}, \begin{pmatrix} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\end{pmatrix}, \begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0\end{pmatrix}, \begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1\end{pmatrix}$$ forms a basis for $H_3$.
– Feng
Jul 20, 2022 at 12:10
• Well. This is clear from $J_3$ .No new information. Jul 20, 2022 at 12:13
• For general $n$, you can also use the same idea to find a basis for $H_n$, so you can prove rigorously $\mathrm{dim} H_n=2n-1$. Although I don't know if this idea fits your purpose: "introduccing a partition of numbers". Just a thought.
– Feng
Jul 20, 2022 at 12:19
• The only integer partitions involved here have two summands, and it's more properly 2 part compositions since, e.g., $a_{12}$ and $a_{21}$ are distinct. It seems unnecessary to invoke the theory of partitions. Aug 2, 2022 at 17:14

Sums of indices can go from $$2$$ to $$2n$$. Define, for $$2\le k\le n$$ the matrix $$M_k$$ that has $$1$$ where $$i+j=k$$ and $$0$$ elsewhere.
It should be easy to prove that $$\{M_k:2\le k\le 2n\}$$ is a basis of your subspace. That's all, you don't need to count the number of nonzero entries in $$M_k$$.
Let's look at a typical matrix in the set when $$n=3$$. The possible sums are $$2,3,4,5,6$$ and we get $$\begin{bmatrix} a & b & c \\ b & c & d \\ c & d & e \end{bmatrix}= a\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}+ b\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}+ c\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}+ d\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}+ e\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ This should give the idea of how to find the basis in the general case.
• @LostinSpace I'd not say it's difficult in this case. First look at what happens for $3\times3$ matrices and make a conjecture. Jul 28, 2022 at 9:15