I.3.6.2: Product Form

There is another way to derive the formulas from the previous section. We use the fact that the algorithmic map $\mathcal{A}$ is a composition of the form $$\mathcal{A}(x)=\mathcal{A}_p(\mathcal{A}_{p-1}(\cdots(\mathcal{A}_1(x))),$$ where each $\mathcal{A}_s$ leaves all blocks, except block $s,$ intact, and changes only the variables in block $s.$ Thus $$\mathcal{A}_s(x)= \begin{bmatrix} x_1\\\vdots\\x_{s-1}\\F_s(x_1,\cdots,x_p)\\x_{s+1}\\\vdots\\x_{p} \end{bmatrix}.$$

Blocks $(u,v)$ of the matrix of partials is (surpressing the dependence on $x$ again for the time being) $$\{\mathcal{DA}_s\}_{uv}\mathop{=}\limits^{\Delta} \begin{cases} \mathcal{D}_vF_u&\text{ if }u=s,\\ I&\text{ if }u=v\not= p,\\ 0&\text{otherwise}. \end{cases}$$ Again, in many cases of interest we have $\{\mathcal{DA}\}_{uv}=0$ if $u=v=s$.

Now clearly, from the chain rule, $$\mathcal{M}=\mathcal{DA}=\mathcal{DA}_p\mathcal{DA}_{p-1}\cdots\mathcal{DA}_1$$ This is the product form of the derivative of the algorithmic map.

For two blocks, and zero diagonal blocks, we have, as in the previous section, $$\mathcal{M}=\mathcal{DA}_2\mathcal{DA}_1=\begin{bmatrix} I&0\\ \mathcal{D}_1F_2&0 \end{bmatrix} \begin{bmatrix} 0&\mathcal{D}_2F_1\\ 0&I \end{bmatrix}= \begin{bmatrix} 0&\mathcal{D}_2F_1\\ 0&\mathcal{D}_1F_2\mathcal{D}_2F_1 \end{bmatrix}.$$ Thus the non-zero eigenvalues of $\mathcal{M}$ are the non-zero eigenvalues of $\mathcal{D}_1F_2\mathcal{D}_2F_1$.

In the general cases with $p$ blocks computing eigenvalues of $\mathcal{M}$ we can use the result that the spectrum of $A_pA_{p-1}\cdots A_1$ is related in a straightforward fashion to the spectrum of the cyclic matrix $$\Gamma(A_1,\cdots,A_p)\mathop{=}\limits^{\Delta}\begin{bmatrix} 0&0&\cdots&0&A_p\\ A_1&0&\cdots&0&0\\ 0&A_2&\cdots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&A_{p-1}&0 \end{bmatrix}.$$ In fact if $\lambda$ is an eigenvalue of $\Gamma(A_1,\cdots,A_p)$ then $\lambda^p$ is an eigenvalue of $A_pA_{p-1}\cdots A_1$, and if $\mu$ is a eigenvalue of $A_pA_{p-1}\cdots A_1$ then the $p$ solutions of $\lambda^p=\mu$ are eigenvalues of $\Gamma(A_1,\cdots,A_p)$.