Hi everyone!

Long time no see. 3 years ago I announced a Telegram channel. Unfortunately, for the last ~1.5 years I had a total lack of inspiration for new blog posts. Well, now I have a glimpse of it once again, so I want to continue writing about interesting stuff. Here's some example:

Let $$$\mathcal F : \mathbb C^n \mapsto \mathbb C^n$$$ be the discrete Fourier transform:

\begin{equation*} (\mathcal F a)_k = \frac{1}{\sqrt n}\sum\limits_{j=0}^{n-1} \omega_n^{jk} a_j, \end{equation*}

where $$$\omega_n = e^{\frac{2\pi i}{n}}$$$ is the $$$n$$$-th complex root of unity. Alse let $$$\mathcal R : \mathbb C^n \mapsto \mathbb C^n$$$ be the reverse operator:

\begin{equation*} (\mathcal R a)_k = a_{(n-k) \bmod n}. \end{equation*}

It is a common fact that double discrete transform yields reverse: $$$\mathcal F^2 a = \mathcal R a$$$. Indeed,

\begin{equation*} (\mathcal F^2 a)_k = \frac{1}{n}\sum\limits_{j_1=0}^{n-1} \omega_n^{j_1 k} \sum\limits_{j_2=0}^{n-1} \omega_n^{j_2 j_1} a_{j_2} = \frac{1}{n} \sum\limits_{j_2=0}^{n-1} a_{j_2} \sum\limits_{j_1=0}^{n-1} \omega_n^{j_1(k+j_2)}=\sum\limits_{j_2=0}^{n-1} a_{j_2} \delta_n(k+j_2) = a_{(n-k) \bmod n}, \end{equation*}

where $$$\delta_n(k)$$$ is equal to $$$1$$$ if $$$k \equiv 0 \pmod n$$$ and to $$$0$$$ otherwise. It is obtained as a power sum:

\begin{equation*} n\delta_n(k) = \sum\limits_{j=0}^{n-1} \omega_n^{jk} = \begin{cases} n&,~ k \equiv 0 \pmod n\newline \frac{1-\omega_n^{kn}}{1-\omega_n^k}=0&,~ \text{otherwise} \end{cases} \end{equation*}

This allows us to understand that $$$\mathcal F^4=I$$$ and eigenvalues of $$$\mathcal F$$$ are $$${1, i, -1, -i}$$$. But what are their multiplicities? A common way to explore matrix's eigenvalues is to look on $$$\text{tr} \mathcal F$$$, $$$\text{tr} \mathcal F^2$$$, $$$\dots$$$, $$$\text{tr} \mathcal F^n$$$:

\begin{equation*} \text{tr} \mathcal F^k = \lambda_1^k + \dots + \lambda_n^k, \end{equation*}

so the sequence $$${\text{tr} \mathcal F, \dots, \text{tr} \mathcal F^n}$$$ uniquely determines the eigenvalues $$${\lambda_1, \dots, \lambda_n}$$$. In our case (Mehta, 1986),

\begin{equation*} \text{tr} \mathcal F^k = 1+\sum\limits_{j=2}^{n}(-i)^{kj}, \end{equation*}

thus eigenvalues of $$$\mathcal F$$$ are $$$1$$$, $$$(-i)^2$$$, $$$(-i)^3$$$, $$$\dots$$$, $$$(-i)^n$$$. Multiplicities of roots of unity here:

\begin{gather*} \begin{matrix} \lfloor\frac{n+4}{4}\rfloor \text{ for } 1,&\lfloor\frac{n+2}{4}\rfloor \text{ for } -1,&\lfloor\frac{n+1}{4}\rfloor \text{ for } i,&\lfloor\frac{n-1}{4}\rfloor \text{ for } -i. \end{matrix} \end{gather*}

As you could guess, this is a "translation" to Codeforces markup of the new post in aforementioned Telegram channel. When the channel was created, I was thinking that it would be for the better, as it better fits for some less related to competitive programming and/or less elaborate posts and I wanted to avoid spamming Codeforces' recent actions.

But well, it turns out I won't produce as many posts as I thought anyway, so posting all of them directly to Codeforces can be an option as well. So, I'll look on how such "example" post would be received here and will probably continue writing like this if people like it. As long, as I have some inspiration :)

P. S. Some time ago I wrote an article about Suffix automaton which was selected as featured article on Russian Wikipedia and was later translated to English Wikipedia as well. I'm really proud of this work and think that it is a very comprehensive reading about theoretical bases of this suffix structure. Feel free to enjoy the reading if, by any chance, the topic is as interesting to you as it is to me.