Set partitions and permanents

Question

Let $a(n)=$ Number of ordered set partitions of $[n]$ such that the smallest element of each block is odd.

Example:

a(3) = 3: 123, 12|3, 3|12.

a(4) = 5: 1234, 124|3, 3|124, 12|34, 34|12.

See A290384 for details.

Motivated by Question 403336 and Question 403386, I consider the permanents $\operatorname{per}(A)$ where $$A=\left[\left\lceil \frac{2j-k}{n+\cos^2(\frac{n\pi}{2})}\right\rceil \right]_{1\le j,k\le n}$$ and $\lceil \cdot\rceil$ is the ceil function.

When $n=1,2,3,4,5,6$, $A=$ $$\left[ \begin {array}{c} 1\end {array} \right] ,$$

$$\left[ \begin {array}{cc} 1&0\\ 1&1\end {array} \right], $$

$$ \left[ \begin {array}{ccc} 1&0&0\\ 1&1&1 \\ 2&2&1\end {array} \right] ,$$

$$ \left[ \begin {array}{cccc} 1&0&0&0\\ 1&1&1&0 \\ 1&1&1&1\\ 2&2&1&1\end {array} \right] ,$$

$$ \left[ \begin {array}{ccccc} 1&0&0&0&0\\ 1&1&1&0&0 \\ 1&1&1&1&1\\ 2&2&1&1&1 \\ 2&2&2&2&1\end {array} \right] ,$$

$$\left[ \begin {array}{cccccc} 1&0&0&0&0&0\\ 1&1&1&0 &0&0\\ 1&1&1&1&1&0\\ 1&1&1&1&1&1 \\ 2&2&1&1&1&1\\ 2&2&2&2&1&1 \end {array} \right] $$ respectively.

Numerical computation indicates that $$\operatorname{per}(A)=a(n)$$ for $1≤n≤21$.

n per(A)
1 1
2 1
3 3
4 5
5 23
6 57
7 355
8 1165
9 9135
10 37313
11 352667
12 1723605
13 19063207
14 108468169
15 1374019539
16 8920711325
17 127336119839
18 928899673425
19 14751357906571
20 119445766884325
21 2088674728868631

Thus, we obtain the following

Conjecture 1. For any positive integer $n$,$$\operatorname{per}(A) = a(n).$$

Question 1. Is this identity correct? How to prove it?

---

EDIT

Let

$$B=\left[\left\lceil \frac{j+k}{n+\cos^2(\frac{n\pi}{2})}\right\rceil \right]_{1\le j,k\le n}$$ where $\lceil \cdot\rceil$ is the ceil function.

When $n=1,2,3,4,5,6$, $B=$

$$ \left[ \begin {array}{c} 2\end {array} \right], $$

$$\left[ \begin {array}{cc} 1&1\\ 1&2\end {array} \right], $$

$$\left[ \begin {array}{ccc} 1&1&2\\ 1&2&2 \\ 2&2&2\end {array} \right] ,$$

$$ \left[ \begin {array}{cccc} 1&1&1&1\\ 1&1&1&2 \\ 1&1&2&2\\ 1&2&2&2\end {array} \right] ,$$

$$ \left[ \begin {array}{ccccc} 1&1&1&1&2\\ 1&1&1&2&2 \\ 1&1&2&2&2\\ 1&2&2&2&2 \\ 2&2&2&2&2\end {array} \right] ,$$

$$ \left[ \begin {array}{cccccc} 1&1&1&1&1&1\\ 1&1&1&1 &1&2\\ 1&1&1&1&2&2\\ 1&1&1&2&2&2 \\ 1&1&2&2&2&2\\ 1&2&2&2&2&2 \end {array} \right] $$ respectively.

We have the following

Conjecture 2. For any positive integer $n$, $$\operatorname{per}(B)=\frac{3-(-1)^n}{2}F(n)$$ where $F(n)$ is the Fubini numbers, i.e. the number of ordered partitions of $[n]$.

It is equivalent to

Conjecture 3. For any positive integer $n$, $$\operatorname{per}(C)=F(n),$$ where $$C=\left[\left\lceil\frac{j+k}{n+1}\right\rceil\right]_{1\le j,k\le n}.$$

Numerical computation indicates that it is true for $1≤n≤21$.

Question 2. Are these new results? How to prove them?

A2: By @Peter Taylor's comments, Conjectures 2 and 3 are known results.

---

ADDED

Today (2021-9-24), I discovered the following interesting arithmetic properties of $a(n)$

Conjecture 4. For any prime $p$,

$$a(n) \equiv a(n+p(p-1)) \pmod p.$$

Noting that $a(1)=a(2)=1$, we have

Conjecture 5. For any prime $p$ , $$a(p^2-p+1) \equiv 1 \pmod p,$$ $$a(p^2-p+2) \equiv 1 \pmod p.$$

Numerical computation indicates that it is true for $2≤p≤19$.

Moreover

Conjecture 6. For any prime $p$ and positive integer $n\geq h \geq 1$,

$$a(n) \equiv a(n+p^h(p-1)) \pmod{p^h}.$$

It is similar to Daniel Barsky's congruence for Fubini numbers.

Daniel Barsky's Congruence. For any prime $p$ and positive integer $n\geq h \geq 1$,

$$F(n) \equiv F(n+p^{h-1}(p-1)) \pmod{p^h},$$

where $F(n)$ is the Fubini numbers.

Question 3. Are these congruences correct? How to prove them?

---

ADDED (2021-9-27)

Claim. Conjecture 4 is true for $2 \leq p \leq 5$.

Proof. Obviously, we have $a(n)\equiv 1 \pmod{2}$. For $3\leq p \leq 5$, we use the following generating function $$\sum_{n\geq 1} a(n)x^n = \sum_{k\geq 1} \frac{(-1)^{k-1}}{\binom{-\frac1x-1}{k-1}\binom{\frac1x-1}k},$$ which is proved by Max Alekseyev.

When $p=3$, \begin{align} \sum_{n\geq 1} a(n)x^n &\equiv \sum_{1 \leq k \leq 2} \frac{(-1)^{k-1}}{\binom{-\frac1x-1}{k-1}\binom{\frac1x-1}k}\\ &=-\frac{x}{x-1}+2\,{\frac {{x}^{3}}{ \left( x+1 \right) \left( 2\,{x}^{2}-3\,x+1 \right) }}\\ &= \sum _{n=0}^{\infty } \left( -{\frac { \left( -1 \right) ^{n}}{3}}+{ \frac {{2}^{n}}{3}} \right) {x}^{n} \pmod{3} \end{align} and $-{\frac { \left( -1 \right) ^{n}}{3}}+{\frac {{2}^{n}}{3}} \pmod{3}$ is a periodic sequence with least period $6$: repeat in the pattern $$1, 1, 0, 2, 2, 0.$$ This leads to $a(n) \equiv a(n+6) \pmod 3.$

Similarly, we have \begin{align} \sum_{n\geq 1} a(n)x^n &\equiv \sum_{1 \leq k \leq 4} \frac{(-1)^{k-1}}{\binom{-\frac1x-1}{k-1}\binom{\frac1x-1}k}\\ &=\sum _{n=0}^{\infty } \left( {\frac {13\,{2}^{n}}{30}}+{\frac {{4}^{n} }{35}}+{\frac { \left( -2 \right) ^{n}}{10}}-{\frac { \left( -3 \right) ^{n}}{35}}-{\frac {13\, \left( -1 \right) ^{n}}{30}}-{\frac { {3}^{n}}{10}} \right) {x}^{n} \pmod{5}, \end{align}

so $a(n) \pmod{5}$ is a periodic sequence with least period $20$: repeat in the pattern $$1, 1, 3, 0, 3, 2, 0, 0, 0, 3, 2, 0, 2, 4, 4, 0, 4, 0, 1, 0.$$ This leads to $a(n) \equiv a(n+20) \pmod 5.$ QED

Moreover, we have the following

Conjecture 7. For any odd prime $p$, \begin{equation} \sum_{n=1}^{p(p-1)}a(n) \equiv \begin{cases} p \pmod{p^2} &\mbox{if $p \equiv 1 \pmod 4$ }\\ 0 \pmod{p^2} &\mbox{if $p \equiv 3 \pmod 4$ } \end{cases}. \end{equation} It is true for $3 \leq p \leq 19$.

---

ADDED (2021-10-04)

Conjecture 8. For any prime $p$, $$\sum_{n=1}^{p(p-1)}\left(\frac{a(n)}{p}\right)\equiv 0 \pmod p,$$ where $\left(\frac{\cdot}p\right)$ is the Legendre symbol.

It is true for $2 \leq p \leq 19$.

Answer 1

Let me outline an approach for computing permanents in these conjectures. For the sake of concreteness, I will prove Conjecture 1 for an odd $n$. The matrix here is the sum of the following two 0-1 matrices (using Iverson bracket notation): $$A:=\big([2j-k \geq 1]\big)_{j,k=1}^n$$ and $$B:=\big([2j-k \geq n+1]\big)_{j,k=1}^n$$ (notice that I intentionally redefine matrices $A$ and $B$). For example, for $n=5$, we have $$A=\begin{bmatrix} 1&0&0&0&0\\ 1&1&1&0&0 \\ 1&1&1&1&1\\ 1&1&1&1&1 \\ 1&1&1&1&1\end{bmatrix} \quad\text{and}\quad B=\begin{bmatrix} 0&0&0&0&0\\ 0&0&0&0&0 \\ 0&0&0&0&0\\ 1&1&0&0&0 \\ 1&1&1&1&0\end{bmatrix} $$ Our goal is to compute $\mathrm{per}(A+B)$ and show that it's equal to $a(n)$.

The crucial observation is that 0-1 matrices can be viewed as boards on which permanent enumerates non-attacking rook placements. Furthermore, our matrices have the shape of Ferrers boards, and the one for $B$ is a sub-board for that of $A$. From now on, I will not distinguish matrices $A$ and $B$ from the corresponding Ferrers boards.

I will use the notation and machinery from my other answer, which computes the number of non-attacking rook placements (i.e., the permanent) for the difference of a Ferrers board with its sub-board. In the current problem, we need to compute the number of placements of $n$ non-attacking rooks in $A$, where each placement comes with multiplicity $2^t$, where $t$ in the number of rooks in $B\subset A$.

Board $A$ has row lengths $$a:=(1,3,5,\dots,n-2,\underbrace{n,n,\dots,n}_{(n+1)/2}),$$ while board $B$ has row lengths $$b:=(\underbrace{0,0,\dots,0}_{(n+1)/2},2,4,\dots,n-1).$$

By inclusion-exclusion here, we have $$\mathrm{per}(A+B) = \sum_{T\subseteq[n]} r_n(A_{\bar T}\| B_T),$$ where $\bar T := [n] \setminus T$ is the complement of $T$. The analog of formula $(\star)$ here gives the following expression: $$\mathrm{per}(A+B) = \sum_{p\in\{0,1\}^n} \prod_{i=1}^n \big(p_i(a_i-\sum_{j=1}^{\tau_A(i)-1} \delta_j) + q_i(b_i-\sum_{j=1}^{\tau_B(i)-1} \delta_j)\big),$$ where $q_i:=1-p_i$ and $$\sigma:=\big(\underbrace{0,0,\dots,0}_{(n+1)/2},1,2,\dots,n-1,\underbrace{n,n,\dots,n}_{(n+1)/2}\big),$$ $$\delta:=\big(q_1,q_2,\dots,q_{\frac{n+1}2},p_1,q_{\frac{n+1}2+1},p_2,q_{\frac{n+1}2+2},\dots,p_{\frac{n-1}2},q_n,p_{\frac{n+1}2},p_{\frac{n+1}2+1},\dots,p_n\big),$$ $$\tau_A:=\big( \frac{n+3}2,\frac{n+7}2, \dots, \frac{3n+1}2, \frac{3n+3}2,\frac{3n+5}2,\dots,2n\big),$$ $$\tau_B:=\big(1,2,\dots,\frac{n+1}2,\frac{n+1}2+2,\frac{n+1}2+4,\dots,\frac{3n-1}2\big).$$

Correspondingly, we have $$\sum_{j=1}^{\tau_A(i)-1} \delta_j = \begin{cases} i-1 + \sum_{j=i}^{\frac{n-1}2+i}q_j, & \text{if}\ i\leq\frac{n-1}2;\\ n - \sum_{j=i}^{n}p_j, & \text{if}\ i\geq\frac{n+1}2. \end{cases}$$ and $$\sum_{j=1}^{\tau_B(i)-1} \delta_j = \begin{cases} \sum_{j=1}^{i-1} q_j & \text{if}\ i\leq\frac{n-1}2;\\ i-1 - \sum_{j=i-\frac{n-1}2}^{i-1}p_j, & \text{if}\ i\geq\frac{n+1}2. \end{cases}$$

The formula then becomes $$\mathrm{per}(A+B) = \sum_{p\in\{0,1\}^n} \prod_{i=1}^{(n-1)/2} \big(p_i(i - \sum_{j=i}^{\frac{n-1}2+i}q_j) - q_i \sum_{j=1}^{i-1} q_j)\big) \prod_{i=(n+1)/2}^n \big(p_i\sum_{j=i}^{n}p_j + q_i(i-n + \sum_{j=i-\frac{n-1}2}^{i-1}p_j)\big).$$

We can see that if $\min\{i\,:\,q_i=1\}\leq\frac{n-1}2$, then the corresponding summand is zero. Hence, we can restrict summation to $(p_i,q_i)=(1,0)$ for all $i\leq\frac{n-1}2$, and further the same holds for $i=\frac{n+1}2$. Shifting indices $i\to \frac{n+1}2+i$, we get the formula: \begin{split} &\mathrm{per}(A+B) = \sum_{p\in\{0,1\}^{\frac{n-1}2}} (1 + \sum_{j=1}^{\frac{n-1}2} p_i) \prod_{i=1}^{(n-1)/2} \big(p_i\sum_{j=i}^{\frac{n-1}2} p_j + q_i (1+\sum_{j=1}^{i-1} p_j)\big)(1+\sum_{j=1}^{i-1} p_j) \\ &=\sum_{p\in\{0,1\}^{\frac{n-1}2}} \bigg( (1 + \sum_{j=1}^{\frac{n-1}2} p_i) \prod_{i=1\atop p_i=1}^{(n-1)/2} \sum_{j=i}^{\frac{n-1}2} p_j\bigg) \cdot \bigg( \prod_{i=1\atop p_i=0}^{(n-1)/2} (1+\sum_{j=1}^{i-1} p_j) \bigg) \cdot \bigg( \prod_{i=1}^{(n-1)/2} (1+\sum_{j=1}^{i-1} p_j) \bigg) \end{split}

---

Now, let's show that this is exactly $a(n)$. More specifically, if we restrict summation to fixed $1 + \sum_{j=1}^{\frac{n-1}2} p_i =: k$, then the sum gives the number of ordered set partitions with $k$ parts.

Think of constructing a set partition by assigning elements $1,2,\dots,n$ in order to some part, and of $p_i$ as the indicator for $2i+1$ being a smallest element in its part (element $1$ has to be the smallest in its part, and this where "$1+$ in the formula comes from). Then

• $(1 + \sum\limits_{j=1}^{\frac{n-1}2} p_i) \prod\limits_{i=1\atop p_i=1}^{(n-1)/2} \sum\limits_{j=i}^{\frac{n-1}2} p_j = k!$ accounts for the order of parts;
• $\prod\limits_{i=1\atop p_i=0}^{(n-1)/2} (1+\sum\limits_{j=1}^{i-1} p_j)$ accounts for assignments of $2i+1$ to one of $1+\sum\limits_{j=1}^{i-1} p_j$ parts, whose smallest elements are smaller than $2i+1$;
• $\prod\limits_{i=1}^{(n-1)/2} (1+\sum\limits_{j=1}^{i-1} p_j)$ accounts for assignments of $2i$ to one of $1+\sum\limits_{j=1}^{i-1} p_j$ parts (whose smallest elements are smaller than $2i$).

Hence, $\mathrm{per}(A+B) = a(n)$. QED

Answer 2

Here is another proof of Conjecture 1, based on a combinatorial interpretation of entries in $A$. The same method works for proving Conjecture 3.

---

The key observation is that each permutation $\sigma\in S_n$ generates distinct odd-leading ordered set partitions, which are counted by a term $\prod_{j=1}^n A'_{j\tau_j}$ in the permanent of a matrix closely related to $A$.

Given a permutation $\sigma \in S_n$, we can construct odd-leading ordered set partitions by going from left to right through $\sigma_1 \sigma_2 \dots \sigma_n$ and inserting boundaries ("dividers") between partition blocks. If $\sigma_i$ is followed by $\sigma_{i+1}$, then the block to which $\sigma_{i}$ belongs may continue if $\sigma_{i}<\sigma_{i+1}$ (i.e. if including $\sigma_{i+1}$ does not break the ordering requirement). If $\sigma_{i+1}$ is odd and therefore may lead a block, then we may insert a divider after $\sigma_i$. If both conditions are true, each option (inserting or not inserting a divider) generates a different partition. If neither condition is true - if $\sigma_{i+1}$ is even and $\sigma_{i+1} < \sigma_{i}$ - then there are no legal partitions generated from this permutation.

For example, for $\sigma = 1234567$, we may optionally place dividers after $2$, $4$, and $6$ for a total of $2^3$ partitions. For $\sigma = 7512346$, we are forced to place dividers after $7$ and $5$ to preserve order within blocks but we may optionally place a divider after $2$, resulting in two partitions $7|5|12346$ and $7|5|12|346$. For $\sigma = 7521346$, there are no legal partitions: we cannot have a divider after $5$ because $2$ is even and may not lead a block, but we also cannot continue the block after $5$ because $2$ is less than $5$.

If $j$ is followed by $k$ in a permutation, then the number of options at that point (continue, insert divider, or neither) are counted by the $n\times n$ matrix $A'$ defined by $$A'_{jk}= \left [ k\text{ odd}\right ] + \left [j < k\right ],$$ using Iverson brackets.

For example for $n = 7$, $$\left[ \begin {array}{ccccccc} 1&1&2&1&2&1&2\\ 1&0&2&1&2&1&2\\ 1&0&1&1&2&1&2\\ 1&0&1&0&2&1&2\\ 1&0&1&0&1&1&2\\ 1&0&1&0&1&0&2\\ 1&0&1&0&1&0&1 \end {array} \right] .$$

By transposing $A'$ and rearranging the rows to put all even-indexed rows before the odd-indexed rows (so e.g. rows $1234567 \mapsto 2461357$), we recover $A$. The permanent is invariant under these operations, so ​$\text{per}(A') = \text{per}(A)$.

We now bijectively construct a permutation $\tau$ from $\sigma$, in order to interpret $A'_{j\tau_j}$ as the number of options for when $j$ is followed by $\tau_j$. We cannot use $A'_{\sigma_i \sigma_{i+1}}$ directly: $A'_{\sigma_n\sigma_1}$ does not reflect that the final block must terminate.

Given a permutation $\sigma$ in one-line notation, let $\tau$ be the unique permutation obtained by inserting parentheses into $\sigma$ to form a permutation in "reverse" canonical cycle notation (list smallest element in each cycle first, sort cycles in decreasing order on the first element). For example, $\sigma=7512346$ maps to $(7)(5)(12346)$, or in one-line notation $\tau = 2346517$. By an analogous variant of Foata's transition lemma, $\sigma \mapsto \tau$ is a bijection.

Note that:

• Any block in an ordered set partition defined from $\sigma$ is completely contained within a single cycle of $\tau$. (A cycle only terminates when the following element is less than the current one, which also means that a block would terminate.)
• For a number $\sigma_i$ not terminating a cycle, $\sigma_i$ is followed by $\tau_{\sigma_i}$.
• For a number $\sigma_i$ terminating a cycle $\sigma_{k}\sigma_{k+1}\dots\sigma_i$, we have that $\tau_{\sigma_i}=\sigma_k$ and $A'_{\sigma_i \tau_{\sigma_i}} = \left [ \sigma_k \text{ odd} \right ]$, and indicates whether $\sigma_k$ may lead a partition block starting there.

Given the above, we may choose to either insert a block divider or continue a block after $\sigma_i$ precisely if $A'_{\sigma_i\tau_{\sigma_i}}=2$. We may not construct a partition if for any $i$, $A'_{\sigma_i\tau_{\sigma_i}} = 0$ (i.e. if a cycle is lead by an even number or if, within a cycle, an even number follows a larger number). The total number of odd-leading ordered set partitions generated from $\sigma$ is therefore $\prod_{i=1}^n A'_{\sigma_i\tau_{\sigma_i}} = \prod_{j=1}^n A'_{j\tau_j}$.

Each partition $P$ is defined by a unique permutation $\sigma$ (because the numbers occur in the same order), and hence each permanent term counts distinct partitions. $a(n)$ can be partitioned into the sum: $$a(n) = \sum_{\sigma \in S_n} \#\left\{\text{partition }P : P \text{ defined by }\sigma\right\} = \sum_{\sigma \in S_n} \prod_{j=1}^n A'_{j\tau_j} = \text{per}(A') = \text{per}(A),$$

which concludes the proof.

---

The proof of Conjecture 3 is similar. Here we are concerned with counting all ordered set partitions, instead of restricting to partitions with odd-leading blocks. We define a matrix $C'$ analogous to $A'$ but without the oddness condition by

$$(C')_{jk}= 1 + \left [j < k\right ],$$

and continue analogously.

Answer 3

The proof of Conjecture 4 is given below

Lemma 1 For any odd prime $p$,

$$\prod_{i=1}^{p-1}(x-i^2) \equiv x^{p-1}-2x^{\frac{p-1}{2}}+1 \pmod p$$ Proof By Lagrange's Theorem we have the relation \begin{align} y^{p-1}-1 \equiv \prod_{i=1}^{p-1}(y-i) \equiv \prod_{i=1}^{p-1}(-y-i) \pmod p\\ \end{align} Then \begin{align} \left(y^{p-1}-1\right)^2 \equiv \prod_{i=1}^{p-1}(y^2-i^2) \pmod p \end{align} Let $y^2=x$, we get Lemma 1.

Lemma 2 For any odd $m$, we have the following identity $$x^{m(m-1)/2}-1=\left(\sum_{k=1}^{m-1}kx^{(m-1)(m-k-1)/2}\right)\left(x^{m-1}-2x^{\frac{m-1}{2}}+1\right)+m(x^{\frac{m-1}{2}}-1).$$ Proof Let $q=x^{(m-1)/2}$ and just compare the coefficients of both sides of the equation.

Proof of Conjecture 4 (Sam Zackrisson and Deyi Chen)

Conjecture 4 holds for $p = 2$ obviously. Suppose $p$ is an odd prime number.

Let $a_k(n)$ = Number of ordered set partitions of $[n]$ with precisely $k$ blocks such that the smallest element of each block is odd. It is not difficult to obtain \begin{equation} a_k(n+2)= \begin{cases} k^2\left(a_k(n)+a_{k-1}(n)\right)&\mbox{if $n$ is even},\\ k^2a_k(n)+k(k-1)a_{k-1}(n)&\mbox{if $n$ is odd}, \end{cases} \end{equation} $a(n)=\sum_{k}a_k(n)$ and $a(n)\equiv \sum_{k=1}^{p-1}a_k(n) \pmod p$. We have $$ \begin{bmatrix} a_1(n+2) \\ a_2(n+2) \\ \vdots\\ a_{p-1}(n+2) \end{bmatrix} =A\begin{bmatrix} a_1(n) \\ a_2(n) \\ \vdots\\ a_{p-1}(n) \end{bmatrix} $$ where $$ A= \begin {bmatrix} 1^2 & 0 & \cdots & 0 & 0 \\ 2^2 & 2^2& \cdots & 0 & 0 \\ \vdots & \vdots& \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & (p-1)^2 &(p-1)^2 \end {bmatrix} \mbox{if $n$ is even} $$ and $$ A= \begin {bmatrix} 1^2 & 0 & \cdots & 0 & 0 \\ 1\cdot2 & 2^2& \cdots & 0 & 0 \\ \vdots & \vdots& \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & (p-2)(p-1) &(p-1)^2 \end {bmatrix} \mbox{if $n$ is odd}. $$ The eigenvalues of the matrix $A$ are $1^2,2^2,\cdots,(p-1)^2$, so the characteristic polynomial of $A$ equals to $$\prod_{i=1}^{p-1}(x-i^2).$$ By Hamilton-Cayley Theorem, we have $$\prod_{i=1}^{p-1}(A-i^2I)=0,$$ where $I$ is the identity matrix. By lemma 1 we deduce $$ A^{p-1}-2A^{\frac{p-1}{2}}+I \equiv \prod_{i=1}^{p-1}(A-i^2I)=0 \pmod p.$$ Combined with Lemma 2, we have $$ A^{p(p-1)/2}-I \equiv p(A^{\frac{p-1}{2}}-1)\equiv 0 \pmod p,$$ i.e. $$ A^{p(p-1)/2} \equiv I \pmod p.$$ So we get $$ \begin{bmatrix} a_1(n+p(p-1)) \\ a_2(n+p(p-1)) \\ \vdots\\ a_{p-1}(n+p(p-1)) \end{bmatrix}\equiv \begin{bmatrix} a_1(n) \\ a_2(n) \\ \vdots\\ a_{p-1}(n) \end{bmatrix} \pmod p $$ which is more than enougth to prove $$ a(n+p(p-1)) \equiv a(n) \pmod p$$ for any prime $p$. QED