Proof that Grover's operator can be written as $D_N=-H_n R_N H_n$

Question

I am interested in showing the validity of the Grover operator. Now there are several ways to show it. One way is with complete induction. It has to be shown that the following relationship applies: $D_N=-H_n\cdot R_N \cdot H_n $

For induction proof I have already formulated the induction assumption and the induction condition.

Induction hypothesis: $N=2$ $$ D_N=-H_n\cdot R_N \cdot H_n, \quad D_N\text{ see Eq. 1 and } R_N \text{ see Eq. 2}$$ $$N=2$$ $$D_2 = -H\cdot R_2 \cdot H = -\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\cdot \begin{pmatrix}-1&0\\0&1\end{pmatrix}\cdot\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix} = \begin{pmatrix}0&1\\1&0\end{pmatrix}$$ Thus: $$D_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}=\begin{pmatrix}0&1\\1&0\end{pmatrix}$$

Induction Prerequisite: For an arbitrary but fixed $N \in \mathbb N $ the statement applies

At the induction step, I'm not sure if that's right. Here I need some support. In the induction step we show the assertion for an $N + 1$. I am not sure if I have to show both $n + 1$ and $N + 1$. At least this is the first idea for an induction step:

$$D_{N+1}=-H_{n+1}R_{N+1}H_{n+1}$$ This is an important statement that you probably need for the induction step: $H_{n+1}$ is equal to $H_1\otimes H_n=\frac{1}{\sqrt{2}}\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}$ then you would have first: $$D_{N+1}=-\frac{1}{\sqrt{2}}\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}\cdot R_{N+1}\cdot \frac{1}{\sqrt{2}}\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}$$

I'm stuck with this step. I am grateful for the answers and hope that the question is clear and understandable.

---

Appendix:

Equation 1: $$D_N = \begin{pmatrix}-1+\frac{2}{N}&\frac{2}{N}&...&\frac{2}{N}\\\frac{2}{N}&-1+\frac{2}{N}&...&\frac{2}{N}\\\vdots&\vdots&\ddots&\vdots\\\frac{2}{N}&\frac{2}{N}&...&-1+\frac{2}{N}\end{pmatrix}$$

Equation 2: $$R_N=\begin{pmatrix}-1&0&...&0\\0&1&\ddots&\vdots\\\cdots&\ddots&\ddots&0\\0&...&0&1\end{pmatrix}$$

Equation 3: $$N=2^n$$

Answer 1

For the proof by induction there isn't really much more than doing some algebra from the equations you already laid out.

Let me write for simplicity $D_N\equiv -\mathbb 1_N + \frac{2}{N} \mathcal I_N$, where $\mathbb 1$ denotes the $N$-dimensional identity matrix, while $\mathcal I_N$ denotes the $N$-dimensional matrix whose every element is 1: $(\mathcal I_N)_{ij}=1\forall i,j$.

We therefore want to prove that $$D_N\equiv-\mathbb 1_N + \frac{2}{N} \mathcal I_N=-H_n R_N H_n.\tag A$$

Proof by induction

Assume (A) to be true for some $N=2^n$, and try to prove it for $n\to n+1$ (note that $n\to n+1$ corresponds to $N\to 2N$): $$ -\mathbb 1_{2N} + \frac{2}{2N} \mathcal I_{2N}=-H_{n+1} R_{2N} H_{n+1}.$$

Observe that $$H_{n+1}=H_n\otimes H_1, \qquad R_{2N}=\begin{pmatrix}R_N & 0\\ 0&\mathbb 1_N\end{pmatrix}.$$ We therefore have $$-H_{n+1} R_{2N} H_{n+1} = - \frac{1}{2}\begin{pmatrix}H_n & H_n\\ H_n& -H_n\end{pmatrix} \begin{pmatrix}R_N & 0\\ 0&\mathbb 1_N\end{pmatrix} \begin{pmatrix}H_n & H_n\\ H_n& -H_n\end{pmatrix} \\ = -\frac{1}{2}\begin{pmatrix}H_n & H_n\\ H_n& -H_n\end{pmatrix} \begin{pmatrix}R_N H_n & R_N H_n\\ H_n& -H_n\end{pmatrix} =-\frac{1}{2}\begin{pmatrix}H_n R_N H_n + \mathbb 1_N & H_n R_N H_n - \mathbb 1_N\\ H_n R_N H_n - \mathbb 1_N& H_n R_N H_n + \mathbb 1_N\end{pmatrix}. $$ By the induction hypothesis, $H_n R_N H_n=\mathbb 1_N-\frac{2}{N}\mathcal I_N$, therefore $$ -\frac{1}{2}\begin{pmatrix}H_n R_N H_n + \mathbb 1_N & H_n R_N H_n - \mathbb 1_N\\ H_n R_N H_n - \mathbb 1_N& H_n R_N H_n + \mathbb 1_N\end{pmatrix} = \begin{pmatrix}-\mathbb 1_N + \mathcal I_N/N & \mathcal I_N/N \\ \mathcal I_N/N & -\mathbb 1_N + \mathcal I_N/N\end{pmatrix}, $$ which is what you wanted to prove.

An alternative direct proof

Here is another way to prove this fact avoiding induction altogether.

We want to prove that $-\mathbb 1_N + \frac{2}{N} \mathcal I_N=-H_n R_N H_n$.

Observe that, by definition, the components of $H_n$ read $$(H_n)_{ij}=\frac{1}{\sqrt{2^n}} (-1)^{i_B\odot j_B},$$ where $i_B$ denotes the binary vector whose elements are the components of $i$ in its binary representation, and $i_B\odot j_B\equiv \oplus_k i_k j_k$ (that is, the modulo-$2$ sum of the products of the binary components of $i$ and $j$).

On the other hand, $R_N$ is written componentwise as $(R_N)_{ij}=\delta_{ij} (-1)^{\delta_{i,0}}$.

The product $H_n R_N H_n$ thus gives $$(H_n R_N H_n)_{ij} = \frac{1}{2^n} \sum_k (-1)^{k\odot(i_B\oplus j_B)} (-1)^{\delta_{k,0}},$$ where $i_B\oplus j_B$ denotes the componentwise bitwise sum of the binary vectors $i_B$ and $j_B$.

Observe now that the $(-1)^{\delta_{k,0}}$ term only affects the $k=0$ element of the sum, and it does so by simply changing its sign from $+1$ to $-1$. In other words, it simply subtracts $2$ from the overall sum, so that we can rewrite the whole thing as $$(H_n R_N H_n)_{ij} = \frac{1}{2^n} \left(\sum_k (-1)^{k\odot(i_B\oplus j_B)} - 2\right).$$ To reach the conclusion you now only need to observe that $$\sum_k (-1)^{k\odot(i_B\oplus j_B)}=N\delta_{i,j}.$$