SOLUTION OF THE SPECTRAL PROBLEM FOR AN ARBITRARY MATRIX \(a_{(nn)}\) BY A GENERALIZED ROTATION METHOD

B. F. Krutoi

(Presented by the scientific seminar of the Department of Engineering and Computational Mathematics)

1. Suppose that we are given an arbitrary square matrix \(a_{(nn)}\), real or complex. Then for such a matrix \(a_{(nn)}\) one can pose the corresponding spectral problem:

Find the sets (spectrum) of eigenvalues \(\lambda\) and eigenvectors \(g_{(n)}=\bar g\) of the matrix \(a_{(nn)}\) satisfying the equation

\[ a_{(nn)}g_{(n)}=\lambda e_{(nn)}g_{(n)}, \tag{1} \]

or, in operator form,

\[ A\bar g=\lambda E\bar g, \tag{1*} \]

where \(A\) and \(E\) are linear operators corresponding to the given matrices \(a_{(nn)}\) and the identity matrix \(e_{(nn)}\) in some reference frame, and \(\lambda\) and \(g\) are the eigenvalues and eigenvectors of the operator \(A\).

To solve the spectral problem posed, we represent equation (1) in the form

\[ \bigl(a_{(nn)}-\lambda e_{(nn)}\bigr)g_{(n)}=0_{(n)}. \tag{2} \]

It follows first of all from this that equation (2) is satisfied if one sets \(g_{(n)}=0_{(n)}\). If, however, the aim is to find a set of nonzero eigenvectors \(g_{(n)x}\), then for this it is necessary to require that the first factor \(a_{(nn)}-\lambda e_{(nn)}\) vanish, which is equivalent to the condition

\[ \left|a_{(nn)}-\lambda e_{(nn)}\right|=0. \tag{3} \]

for the corresponding determinant \(\left|a_{(nn)}-\lambda e_{(nn)}\right|\).

After expanding determinant (3), we obtain an algebraic equation of degree \(n\) with unknown \(\lambda\),

\[ \left|a_{(nn)}-\lambda e_{(nn)}\right| =\sum_{\nu=0}^{n} b_\nu \lambda^\nu=0, \tag{3a} \]

which always has \(n\) roots \(\lambda_s\), some of which may possibly be complex pairs of the form \(a_x\pm i\beta_x\). Moreover, among the \(n\) roots

\(\lambda_s\) of equation (3a) may also be equal to one another. Therefore the number \(r\) of roots \(\lambda_\beta\) of equation (3a) that are distinct from one another may also be less than \(n\): \(r \le n\).

If we substitute \(r \le n\) distinct roots \(\lambda_\beta\) into the matrix equation (2), we obtain a bundle of \(r\) equations of the form

\[ a_{(nn)}g_{(n)\beta}=\lambda_\beta e_{(nn)}g_{(n)\beta},\quad (\beta=1,2,\ldots,r\le n) \tag{4} \]

with respect to \(r \le n\) corresponding eigenvectors \(g_{(n)\beta}\), which may also be represented by the matrix equation

\[ a_{(nn)}g_{(nr)}=e_{(nn)}g_{(nr)}\lambda_{(rr)}=g_{(nr)}\lambda_{(rr)} \quad (r\le n), \tag{4*} \]

where in (4) and (4*)

\[ 1)\quad g_{(n)\beta}= \begin{bmatrix} g_{1\beta}\\ g_{2\beta}\\ \vdots\\ g_{\nu\beta}\\ \vdots\\ g_{n\beta} \end{bmatrix}, \quad 2)\quad \lambda_{(rr)}= \begin{bmatrix} \lambda_1 & 0 & \ldots & 0 & \ldots & 0\\ 0 & \lambda_2 & \ldots & 0 & \ldots & 0\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\ 0 & 0 & \lambda_\beta & \ldots & 0\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\ 0 & 0 & \ldots & 0 & \ldots & \lambda_r \end{bmatrix}. \tag{5} \]

Since each \(\beta\)-th equation of the bundle (4) with the unknown eigenvector \(g_{(n)\beta}\) is homogeneous, one of the components \(g_{\nu\beta}\) of this vector will be arbitrary, and we shall assume that

\[ g_{(n)\beta}=1,\quad (\beta=1,2,\ldots,r\le n). \tag{6} \]

If \(r=n\), then in equation (4*) we have \(g_{(nr)}=g_{(nn)}\), \(\lambda_{(rr)}=\lambda_{(nn)}\), and we then find that

\[ \lambda_{(nn)}=g_{(nn)}^{-1}a_{(nn)}g_{(nn)} =\varkappa_{(nn)}a_{(nn)}\bar g_{(nn)}=\omega_{(nn)}. \tag{7} \]

Hence it is evident that if \(r=n\), then in the reference frame of their \(n\) eigenvectors \(g_{(n)\beta}\) the initial matrix \(a_{(nn)}\) becomes the diagonal \(\lambda_{(nn)}=\omega_{(nn)}\) with the simplest structure (5).

If, however, \(r<n\), then we set the task of finding, for the \(r\) eigenvectors \(g_{(n)\beta}\), another \(n-r\) independent adjoined vectors \(f_{(n)j}\), \(j=r+1,r+2,\ldots,n\), such that, in the reference frame consisting of \(r\) eigenvectors \(g_{(n)\beta}\) and \(n-r\) adjoined vectors \(f_{(n)j}\), the transformed matrix \(\omega_{(nn)}\), where

\[ \omega_{(nn)}=\{g_{(nr)}f_{(n.n-r)}\}^{-1}a_{(nn)}[g_{(nr)}f_{(n.n-r)}], \tag{8} \]

would have the simplest possible form.

Following Jordan [1], we shall determine these \(n-r\) adjoined vectors \(f_{(n)j}\) in parts, assigning to each eigenvector \(g_{(n)\beta}\), generated by the eigenvalue \(\lambda_\beta\) of multiplicity \(d_\beta\), another \(d_\beta-1\) adjoined vectors \(f_{(n)j}=g^{\alpha}_{(n)\beta}\), \(\alpha=2,3,\ldots,d_\beta\), and setting \(g_{(n)\beta}=g^1_{(n)\beta}\).

In order that all \(n\) vectors \(g_{(n)\beta}=g^1_{(n)\beta},\ g^\alpha_{(n)\beta}\) be linearly independent and that the matrix \(\omega_{(nn)}\) transformed according to (8) have the simplest structure, Jordan proposed determining each \(\beta\)-th collection of \(d_\beta\) vectors \(g_{(n)\beta}=g^1_{(n)\beta},\ g^\alpha_{(n)\beta}\) from the following system of \(d_\beta\) vector equations

\[ \left\{ \begin{aligned} A\bar g_{\beta 1}&=\lambda_\beta \bar g_{\beta 1}+0\bar g_{\beta 2}+0\bar g_{\beta 3}+\cdots+0\bar g_{\beta\cdot\partial_\beta-1}+0\bar g_{\beta\cdot\partial_\beta}\\ A\bar g_{\beta 2}&=1\bar g_{\beta 1}+\lambda_\beta \bar g_{\beta 2}+0\bar g_{\beta 3}+\cdots+0\bar g_{\beta\cdot\partial_\beta-1}+0\bar g_{\beta\cdot\partial_\beta}\\ A\bar g_{\beta 3}&=0\bar g_{\beta 1}+1\bar g_{\beta 2}+\lambda_\beta \bar g_{\beta 3}+\cdots\quad 0\bar g_{\beta\cdot\partial_\beta-1}+0\bar g_{\beta\cdot\partial_\beta}\\ &\cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\\ A\bar g_{\beta\cdot\partial_\beta}&=0\bar g_{\beta 1}+0\bar g_{\beta 2}+0\bar g_{\beta 3}+\cdots 1\bar g_{\beta\cdot\partial_\beta-1}+\lambda_\beta \bar g_{\beta\cdot\partial_\beta}. \end{aligned} \right. \tag{9**} \]

Here \(A\) is a linear operator, to which, in the initial reference basis, there corresponds the matrix \(a_{(nn)}\), while in the basis consisting of \(r\) eigenvectors \(g_{(n)\beta}=\bar g_\beta=\bar g_{\beta 1}\) and \(n-r\) adjoined vectors \(f_{(n)j}=g_{(n)j}^{\alpha}=\bar g_{\beta\alpha}\), there corresponds the matrix \(\omega_{(nn)}\), defined according to (8).

If, further, the set (9**) of \(\partial_\beta\) vector equations is written in a more compressed form,

\[ \begin{aligned} A[\bar g_{\beta 2}\cdots \bar g_{\beta\alpha}\cdots \bar g_{\beta\cdot\partial_\beta}]^{*} &= \begin{bmatrix} \lambda_\beta & 0 & 0\cdots 0 & 0\cdots 0 & 0\\ 1_{21} & \lambda_\beta & 0\cdots 0 & 0\cdots 0 & 0\\ 0 & 1_{32} & \lambda_\beta\cdots 0 & 0\cdots 0 & 0\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ 0 & 0 & 0\cdots 1_{\alpha,\alpha-1}\lambda_\beta\cdots 0 & 0\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ 0 & 0 & 0\cdots 0 & 0\cdots 1 & \lambda_\beta \end{bmatrix} \begin{bmatrix} \bar g_{1\beta}\\ \bar g_{2\beta}\\ \cdot\\ \cdot\\ \bar g_{\alpha\beta}\\ \cdot\\ \cdot\\ \bar g_{\partial_\beta\cdot\beta} \end{bmatrix} \\ &= [\bar g_{\beta 1}\bar g_{\beta 2}\cdots \bar g_{\beta\alpha}\cdots \bar g_{\beta\cdot\partial_\beta}]^{*} \begin{bmatrix} \lambda_\beta & 1_{12}^{*} & 0 & \cdots & 0 & 0\cdots 0\\ 0 & \lambda_\beta & 1_{23}^{*} & \cdots & 0 & 0\cdots 0\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ 0 & 0 & 0\cdots & \lambda_\beta & 1_{\alpha,\alpha-1}^{*}\cdots 0\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ 0 & 0 & 0\cdots 0 & 0\cdots \lambda_\beta \end{bmatrix}, \end{aligned} \tag{9*} \]

then to the vector-matrix equation (9*) there will correspond the following matrix equation

\[ a_{(nn)}g_{(n\cdot\partial_\beta)}=g_{(n\cdot\partial_\beta)}\omega_{(\partial_\beta\cdot\partial_\beta)},\qquad (\beta=1,2,\ldots,r\le n), \tag{9} \]

where it is denoted

\[ 1)\quad g_{(n\cdot\partial_\beta)} = [g_{(n)1}^{\beta}g_{(n)2}^{\beta}\cdots g_{(n)\alpha}^{\beta}\cdots g_{(n)\partial_\beta}^{\beta}], \]

\[ 2)\quad \omega_{(\partial_\beta\cdot\partial_\beta)} = \begin{bmatrix} \lambda_\beta & 1 & 0\cdots 0 & 0\cdots 0\\ 0 & \lambda_\beta & 1 & 0 & 0 & 0\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ 0 & 0 & 0\cdots \lambda_\beta & 1\cdots 0\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ 0 & 0 & 0\cdots 0 & 0\cdots \lambda_\beta \end{bmatrix}. \tag{10} \]

The cell \(\omega_{(\partial_\beta\cdot\partial_\beta)}\) of the simple structure (10) is called a Jordan box.

From the investigation carried out it now follows that if in the transforming matrix \([g_{(nr)}f_{(n,n-r)}]\) from equality (8) we rearrange the columns in accordance with the Jordan proposal (9**), then we obtain the transforming matrix \(g_{(nn)}\), which will have the following structure

\[ g_{(nn)}=[g_{(n\cdot\partial_1)}g_{(n\cdot\partial_2)}\cdots g_{(n\cdot\partial_\beta)}\cdots g_{(n\cdot\partial_\lambda)}],\qquad (r\le n). \tag{11} \]

Then, instead of expression (8), for computing the matrix \(\omega_{(nn)}\) we find an equality of the same form

\[ \omega_{(nn)}=g^{-1}_{(nn)}a_{(nn)}g_{(nn)}=\mathfrak{X}_{(nn)}a_{(nn)}g_{(nn)} . \tag{12} \]

Let us clarify the structure of the matrix \(\omega_{(nn)}\) computed according to (12). To this end, we add all \(r\) vector equations (9). Then we obtain

\[ \sum_{\beta=1}^{r} a_{(nn)}g_{(n\cdot \theta_\beta)} = \sum_{\beta=1}^{r} g_{(n\cdot \theta_\beta)}\omega_{(\theta_\beta\cdot\theta_\beta)} = \sum_{\beta=0}^{n} g_{(n\cdot \theta_\beta)}\omega_{(\theta_\beta\cdot\theta_\alpha)},\quad (r\le n), \]

where

\[ \omega_{(\theta_\beta\cdot\theta_\beta)} = \begin{cases} \omega_{(\theta_\beta\cdot\theta_\beta)}, & \text{if } \alpha=\beta,\\ 0_{(\theta_\beta\cdot\theta_\alpha)}, & \text{if } \alpha\ne\beta. \end{cases} \tag{13} \]

It follows from this that the matrix \(\omega_{(nn)}=[\omega_{(\theta_\beta\cdot\theta_\alpha)}]_{1}^{r}\), defined according to (12), has the following structure:

\[ \omega_{(nn)}= \begin{bmatrix} \omega_{(\theta_1\cdot\theta_1)} & 0_{(\theta_1\cdot\theta_2)} & \cdots & 0_{(\theta_1\cdot\theta_\beta)} & \cdots & 0_{(\theta_1\cdot\theta_r)}\\ 0_{(\theta_2\cdot\theta_1)} & \omega_{(\theta_2\cdot\theta_2)} & \cdots & 0_{(\theta_2\cdot\theta_\beta)} & \cdots & 0_{(\theta_2\cdot\theta_r)}\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\ 0_{(\theta_\beta\cdot\theta_1)} & 0_{(\theta_\beta\cdot\theta_2)} & \cdots & \omega_{(\theta_\beta\cdot\theta_\beta)} & \cdots & 0_{(\theta_\beta\cdot\theta_r)}\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\ 0_{(\theta_r\cdot\theta_1)} & 0_{(\theta_r\cdot\theta_2)} & \cdots & 0_{(\theta_r\cdot\theta_\beta)} & \cdots & \omega_{(\theta_r\cdot\theta_r)} \end{bmatrix}, \quad (r\le n) \tag{14} \]

with Jordan blocks \(\omega_{(\theta_\beta\cdot\theta_\beta)}\) of the simplest form (10).

1. We have given a solution of the spectral problem (1), reducing it to the sequence of equations \((3a)\), \((4^*)\), (9)

\[ 1)\ \left|a_{(nn)}-\lambda e_{(nn)}\right| =\sum_{\nu=0}^{n} b_\nu\lambda^\nu=0;\qquad 2)\ a_{(nn)}g_{(nr)}=g_{(nr)}\lambda_{(rr)},\quad (r\le n) \tag{15} \]

\[ 3)\ a_{(nn)}g_{(n\cdot\theta_\beta)} = g_{(n\cdot\theta_\beta)}\omega_{(\theta_\beta\cdot\theta_\beta)},\qquad (\beta=1,2,\ldots,\ r\le n) \]

with the concluding representation (12)

\[ \omega_{(nn)}=g^{-1}_{(nn)}a_{(nn)}g_{(nn)}=\mathfrak{X}_{(nn)}a_{(nn)}g_{(nn)} \tag{12} \]

for the desired matrix of simplest structure \(\omega_{(nn)}\).

However, such a way of solving the spectral problem (1) is expedient only for \(n\le 4\). If \(4<n\le 49\), then in solving this problem on digital computers of the BESM-4 type one must apply Danilevsky’s method [2], for which ready-made programs in the language “Algol-60” are available on these machines.

Finally, for \(n>15\text{--}20\) it is expedient, and for \(n>49\) it is absolutely necessary, to apply one or another method of successive approximations to solve the spectral problem (1). These methods yield the transforming matrix \(g_{(nn)}\) and the matrix of simplest structure \(\omega_{(nn)}\), bypassing the preliminary step—quite infeasible for large \(n\)—of expanding the determinant \(\left|a_{(nn)}-\lambda e_{(nn)}\right|\) into the corresponding polynomial \(\sum_{\nu=0}^{n} b_\nu\lambda^\nu\).

One method of this kind was proposed by V. V. Voevodin in [3], but a substantial shortcoming of his method is the necessity of a two-stage transformation of the original matrix \(a_{(nn)}\): first, reductions of the dimensions \(|a_{rs}|\) of all elements \(a_{rs}\) of the matrix \(a_{(nn)}\) are achieved, its “trimming” is performed, and then the method of rotations is applied in order to reduce the “trimmed” matrix \(\tilde a_{(nn)}\) to the simplified form \(\omega_{(nn)}\). In addition, Voevodin gives only a weak justification for the necessity of preliminary “trimming” of the original matrix \(a_{(nn)}\), and the algorithm for passing from \(a_{(nn)}\) to \(\tilde a_{(nn)}\) is too complicated.

In reality, Voevodin’s idea of first “trimming” the original matrix \(a_{(nn)}\) and only then applying the method of rotations is caused by the weak convergence of that simplest version of the rotation method which was proposed by Jacobi in the last century for the special case of a symmetric or Hermitian matrix \(a_{(nn)}\) [2].

1. If Voevodin had managed to generalize Jacobi’s method in a proper way to the solution of the spectral problem in the case of an arbitrary matrix \(a_{(nn)}\), then the preliminary passage from the original matrix \(a_{(nn)}\) to the “trimmed” matrix \(\tilde a_{(nn)}\) would not have been needed either.

Therefore we shall now set about finding such a generalization for Jacobi’s original method, one which would give a solution of the spectral problem for any matrix \(a_{(nn)}\) and would possess a sufficient rate of convergence, controllable by us. The essence of the proposed generalized Jacobi method is as follows.

1. First of all, for all rows \(j=1,2,\ldots,n\) of the original matrix \(a_{(nn)}\), we form the sums \(Ц_j^{0}\), where

\[ 1)\quad Ц_j^{(0)}=\sum_{\substack{k=1\\ k\ne j}}^n |a_{jk}|^2, \qquad 2)\quad |a_{jk}|^2=a_{jk}\overline{a}_{jk}=(\alpha_{jk}\pm i\beta_{jk})^2=\alpha_{jk}^2+\beta_{jk}^2, \tag{16} \]

and among these sums \(Ц_j^{(0)}\) we single out the \(m<n\) largest ones
\(Ц_s^{(0)}, Ц_t^{(0)},\ldots, Ц_w^{(0)}\).
Then, in the original matrix \(a_{(nn)}\), we select the \(m^2\) elements \(a_{\mu\nu}\) lying at the intersections of the selected \(m\) rows \(\mu=s,t,\ldots,w\) and the corresponding \(m\) columns \(\nu=s,t,\ldots,w\), and arrange the indicated \(m^2\) numbers \(a_{\mu\nu}\) in the form of an auxiliary matrix \(a_{(mm)}^{st\ldots w}=a_{(mm)}^{(0)}\), with the same mutual arrangement of rows and columns as in the original matrix \(a_{(nn)}\). Thus,

\[ a_{(mm)}^{st\ldots w}=a_{(mm)}^{(0)}= \begin{bmatrix} a_{ss} & a_{st} & \ldots & a_{s\nu} & \ldots & a_{sw}\\ a_{ts} & a_{tt} & \ldots & a_{t\nu} & \ldots & a_{tw}\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\ a_{\mu s} & a_{\mu t} & \ldots & a_{\mu\nu} & \ldots & a_{\mu w}\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\ a_{ws} & a_{wt} & \ldots & a_{w\nu} & \ldots & a_{ww} \end{bmatrix}. \tag{17} \]

Now, for the indicated auxiliary matrix \(a_{(mm)}^{st\ldots w}=a_{(mm)}^{(0)}\), one must calculate, by Danilevsky’s method, the set of distinct eigenvalues \(\lambda_\beta\) of multiplicity \(o_\beta\) and the corresponding matrix \(g_{(mm)}^{(0)}\) of principal \(g_{(m)1}^{\beta}\) and associated \(g_{(m)1}^{\beta_\alpha}\) vectors. Next, we recalculate the resulting matrix \(g_{(mm)}^{(0)}\) into the reduced \(\tilde g_{(mm)}^{(0)}\), whose columns \(\tilde g_{(m)x}\) satisfy the condition \(|g_{(m)x}|=1\). In addition, for the redu—

of the matrix \(\tilde g^{(0)}_{(mm)}\), we compute its inverse matrix
\((\tilde g^{(0)}_{(mm)})^{-1}=\tilde{\varkappa}^{(0)}_{(mm)}\). Finally, with the aid of the reduced matrices \(\tilde g^{(0)}_{(mm)}\) and \(\tilde{\varkappa}^{(0)}_{(mm)}\), we construct the corresponding transforming matrices \(\tilde g^{(0)}_{(nn)}\) and \(\tilde{\varkappa}^{(0)}_{(nn)}\). This construction of the matrices \(\tilde g^{(0)}_{(nn)}\) and \(\tilde{\varkappa}^{(0)}_{(nn)}\) from the found matrices \(\tilde g^{(0)}_{(mm)}\) and \(\tilde{\varkappa}^{(0)}_{(mm)}\) is carried out as follows. If the matrices \(\tilde g^{(0)}_{(mm)}\) and \(\tilde{\varkappa}^{(0)}_{(mm)}\) are represented in the form

\[ \tilde g^{(0)}_{(mm)}= \left[ \begin{array}{cccc} \tilde g_{ss}\tilde g_{st}\ldots & \tilde g_{sv}\ldots & \tilde g_{sw}\\ \tilde g_{ts}\tilde g_{tt}\ldots & \tilde g_{tv}\ldots & \tilde g_{tw}\\ \cdot\ \cdot\ \cdot\ \cdot & \cdot & \cdot\\ \tilde g_{\mu s}\tilde g_{\mu t}\ldots & \tilde g_{\mu v}\ldots & \tilde g_{\mu w}\\ \cdot\ \cdot\ \cdot\ \cdot & \cdot & \cdot\\ \tilde g_{ws}\tilde g_{wt}\ldots & \tilde g_{wv}\ldots & \tilde g_{ww} \end{array} \right], \quad |\tilde g_{(m)x}|=1, \quad (x=1,2,\ldots,m) \tag{18.1} \]

\[ [\tilde g^{(0)}_{(mm)}]^{-1}=\tilde{\varkappa}^{(0)}_{(mm)}= \left[ \begin{array}{cccc} \tilde{\varkappa}_{ss}\tilde{\varkappa}_{st}\ldots & \tilde{\varkappa}_{sv}\ldots & \tilde{\varkappa}_{sw}\\ \tilde{\varkappa}_{ts}\tilde{\varkappa}_{tt}\ldots & \tilde{\varkappa}_{tv}\ldots & \tilde{\varkappa}_{tw}\\ \cdot\ \cdot\ \cdot\ \cdot & \cdot & \cdot\\ \tilde{\varkappa}_{\mu s}\tilde{\varkappa}_{\mu t}\ldots & \tilde{\varkappa}_{\mu v}\ldots & \tilde{\varkappa}_{\mu w}\\ \cdot\ \cdot\ \cdot\ \cdot & \cdot & \cdot\\ \tilde{\varkappa}_{ws}\tilde{\varkappa}_{wt}\ldots & \tilde{\varkappa}_{wv}\ldots & \tilde{\varkappa}_{ww} \end{array} \right], \quad |\tilde{\varkappa}_{(m)x}|=1 \quad (x=1,2,\ldots,n) \tag{18.2} \]

then the transforming matrix \(\tilde g^{(0)}_{(nn)}\) generated by the auxiliary matrix \(\tilde g_{(mm)}\) is defined in the following manner:

\[ \tilde g^{(0)}_{(nn)}= \left[ \begin{array}{cccccccc} e_{11}e_{12}\ldots e_{1s}\ldots e_{1t}\ldots e_{1v}\ldots e_{1w}\ldots e_{1,n-1}\ e_{1n}\\ e_{21}e_{22}\ldots e_{2s}\ldots e_{2t}\ldots e_{2v}\ldots e_{2w}\ldots e_{2,n-1}\ e_{2n}\\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\\ e_{s1}e_{s2}\ldots \tilde g_{ss}\ldots \tilde g_{st}\ldots \tilde g_{sv}\ldots \tilde g_{sw}\ldots e_{s,n-1}\ e_{sn}\\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\\ e_{t1}e_{t2}\ldots \tilde g_{ts}\ldots \tilde g_{tt}\ldots \tilde g_{tv}\ldots \tilde g_{tw}\ldots e_{t,n-1}\ e_{tn}\\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\\ e_{\mu1}e_{\mu2}\ldots \tilde g_{\mu s}\ldots \tilde g_{\mu t}\ldots \tilde g_{\mu v}\ldots \tilde g_{\mu w}\ldots e_{\mu,n-1}\ e_{\mu n}\\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\\ e_{w1}e_{w2}\ldots \tilde g_{ws}\ldots \tilde g_{wt}\ldots \tilde g_{wv}\ldots \tilde g_{ww}\ldots e_{w,n-1}\ e_{wn}\\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\\ e_{n-1,1}\ e_{n-1,2}\ldots e_{n-1,s}\ldots e_{n-1,t}\ldots e_{n-1,v}\ldots e_{n-1,w}\ldots e_{n-1,n-1}e_{n-1,n}\\ e_{n1}e_{n2}\ldots e_{ns}\ldots e_{nt}\ldots e_{nv}\ldots e_{nw}\ldots e_{n,n-1}\ e_{nn} \end{array} \right], \quad e_{\lambda x}= \begin{cases} 1, & x=\lambda,\\ 0, & x\ne\lambda. \end{cases} \tag{19.0} \]

and the inverse transforming matrix will have the same structure,

\[ [\tilde g^{(0)}_{(nn)}]^{-1}=\tilde{\varkappa}^{(0)}_{(nn)}, \]

obtained by replacing in (19.0) the reduced matrix \(\tilde g^{(0)}_{(mm)}\) by its inverse \(\tilde{\varkappa}^{(0)}_{(mm)}\).

Having constructed the transforming matrices \(\tilde g^{(0)}_{(nn)}\) and \(\tilde{\varkappa}^{(0)}_{(nn)}\) of the first approximation, we compute, according to (12), the corresponding first approximation
\[ \omega^{(1)}_{(nn)}=a^{(1)}_{(nn)} \]
for the simplified matrix \(\omega_{(nn)}\).

\[ \omega_{(nn)}^{(1)}=\left(\widetilde{g}_{(nn)}^{(0)}\right)^{-1}a_{(nn)}\widetilde{g}_{(nn)}^{(0)} =\widetilde{\varkappa}_{(nn)}^{(0)}\omega^{(0)}\widetilde{g}_{(nn)}^{(0)} =a_{(nn)}^{(1)}, \tag{20.1} \]

where we have denoted \(a_{(nn)}=\omega_{(nn)}^{(0)}=a_{(nn)}^{(0)}\).

Let us clarify the structure of the matrix found, \(\omega_{(nn)}^{(1)}=a_{(nn)}^{(1)}\). To this end, let us note that if, instead of transformation (20), we had taken the transformation

\[ \omega_{(mm)}^{(1)}=\widetilde{\varkappa}_{(mm)}^{(0)}a_{(mm)}^{rs\ldots w}\widetilde{g}_{(mm)}^{(0)} =\widetilde{\varkappa}_{(mm)}^{(0)}a_{(mm)}^{(0)}g_{(mm)}^{(0)}, \tag{21.1} \]

then we would obtain the matrix \(\omega_{(mm)}^{(1)}\) in the purely diagonal form (5.2), when all \(m\) eigenvalues \(\lambda_s\) are distinct; or else we would obtain the matrix \(\omega_{(mm)}^{(1)}\), somewhat complicated by Jordan boxes (10.2), when multiple \(\lambda_s\) occur among the eigenvalues. The general transformation (20) differs from the particular transformation (21) in two respects:

a) the matrix \(a_{(mm)}^{rs\ldots w}\) is replaced by the matrix \(a_{(nn)}\);

b) instead of the matrices \(\widetilde{g}_{(mm)}^{(0)},\ \widetilde{\varkappa}_{(mm)}^{(0)}\), the matrices \(\widetilde{g}_{(nn)}^{(0)},\ \widetilde{\varkappa}_{(nn)}^{(0)}\) are taken, which are obtained from the identity matrix \(e_{(nn)}\) if its entries \(e_{\mu\nu}\) are assigned the corresponding values \(\widetilde{g}_{\mu\nu},\ \widetilde{\varkappa}_{\mu\nu}\) that constitute the matrices \(\widetilde{g}_{(mm)}^{(0)},\ \widetilde{\varkappa}_{(mm)}^{(0)}\).

Therefore, in the general matrix \(\omega_{(nn)}^{(1)}\), at the corresponding positions \(\mu\nu\) there will stand the same values \(\omega_{\mu\nu}^{(1)}=\lambda_s,\ 1,\ 0\) as in the particular matrix \(\omega_{(mm)}^{(1)}\). At all the other positions of the matrix \(\omega_{(nn)}^{(1)}\) there will be some other numbers \(\omega_{\tau\sigma}^{(1)}\), computed according to (20.1),

\[ \omega_{\tau\sigma}^{(1)} =\sum_{\chi=1}^{n}\sum_{\rho=1}^{n} \varkappa_{\tau\chi}^{(1)}a_{\chi\rho}g_{\rho\sigma}^{(1)} . \tag{22} \]

Thus, one may say that the general matrix \(\omega_{(nn)}^{(1)}\) reproduces, at the corresponding positions \(\mu\nu\), the particular matrix \(\omega_{(mm)}^{(1)}\).

Having clarified the structure of the first approximation \(\omega_{(nn)}^{(1)}=a_{(nn)}^{(1)}\) for the simplified matrix \(\omega_{(nn)}\), in the same way we compute the second approximation \(\omega_{(nn)}^{(2)}\) of this matrix \(\omega_{(nn)}\). To this end, for the obtained matrix \(\omega_{(nn)}^{(1)}=a_{(nn)}^{(1)}\) we calculate, over all rows \(j=1,2,\ldots,n\), the sums \(Ц_j^{(1)}\), which, however, unlike the sums \(Ц^{(0)}\), are determined taking into account the fact that the entries \(\omega_{s,s+1}^{(1)}=a_{s,s+1}^{(1)}\) of the matrix \(\omega_{(nn)}^{(1)}=a_{(nn)}^{(1)}\) are equal to \(+1\) if the corresponding eigenvalue \(\lambda_s\) is a multiple \(\hat{\lambda}_3\). Therefore the indicated sums \(Ц_j^{(1)}\) must be calculated as follows:

\[ Ц_j^{(1)}=\sum_{\chi=k}^{n}\left|a_{kj}^{(1)}\right|^2,\quad k\ne \begin{cases} j, & \text{if } a_{j,j+1}^{(1)}=0,\\ j\cap j+1, & \text{if } a_{j,j+1}^{(1)}=1. \end{cases} \tag{23.1} \]

Next, among the sums obtained \(Ц_j^{(1)}\), the \(m\) largest are selected,
\(Ц_c^{(1)}, Ц_d^{(1)},\ldots, Ц_\mu^{(1)},\ldots, Ц_k^{(1)}\), and then from \(a_{(nn)}^{(1)}\) one forms the particular matrix \(a_{(mm)}^{cd\ldots k}=a_{(mm)}^{(1)}\), whose entries \(a_{\mu\nu}^{(1)}\) are located at the intersection of the \(m\) rows \(\mu=c,d,\ldots,k\) and the \(m\) columns \(\nu=c,d,k\) of the matrix \(a_{(nn)}^{(1)}\). Now, for the constructed matrix \(a_{(mm)}^{cd\ldots k}=a_{(mm)}^{(1)}\), we find by the method

Danilevskii eigenvalues \(\lambda_s\), some of which \(\lambda_\beta\) may be multiple, and form the partial transforming matrix \(g^{(1)}_{(mm)}\) from the principal \(\bar g^{(1)}_\beta\) and adjoint \(\bar g^{(1)}_\alpha\) vectors of the matrix \(a^{(1)}_{(mm)}\).

Then, for the matrix \(g^{(1)}_{(mm)}\), we find its reduced representation \(\tilde g^{(1)}_{(mm)}\), where the columns \(\tilde g^{(1)}_{(m)\chi}\) satisfy the condition \(\left|\tilde g^{(1)}_{(m)\chi}\right|=1\), and compute the inverse matrix \((\tilde g^{(1)}_{(mm)})^{-1}=\tilde{\mathfrak{x}}^{(1)}_{(mm)}\). Finally, we pass from the matrices \(\tilde g^{(1)}_{(mm)}\) and \(\tilde{\mathfrak{x}}^{(1)}_{(mm)}\) to the general transforming matrices \(\tilde g^{(1)}_{(nn)}\) and \(\tilde{\mathfrak{x}}^{(1)}_{(nn)}\) by assigning to the components \(e_{\mu\nu}\) of the identity matrix \(e_{(nn)}\) the corresponding values of \(\tilde g^{(1)}\) and \(\tilde{\mathfrak{x}}^{(1)}_{\mu\nu}\) that occur in the partial matrices \(\tilde g^{(1)}_{(mm)}\) and \(\tilde{\mathfrak{x}}^{(1)}_{(mm)}\).

Having constructed the general transforming matrices \(\tilde g^{(1)}_{(nn)}\) and \(\tilde{\mathfrak{x}}^{(1)}_{(nn)}\), we can now obtain the second approximation \(\omega^{(2)}_{(nn)}=a^{(2)}_{(nn)}\) to the desired simplified matrix \(\omega_{(nn)}\), using an expression of the same form as (20.1):

\[ \omega^{(2)}_{(nn)}=(\tilde g^{(1)}_{(nn)})^{-1}a^{(1)}_{(nn)}\tilde g^{(1)}_{(nn)} =\tilde{\mathfrak{x}}^{(1)}_{(nn)}a^{(1)}_{(nn)}\tilde g^{(1)}_{(nn)} =a^{(2)}_{(nn)}. \tag{20.2} \]

In the same way we compute the third \(\omega^{(3)}_{(nn)}\), the fourth \(\omega^{(4)}_{(nn)}\), and all subsequent \(\omega^{(s)}_{(nn)}\) approximations to the desired simplified matrix \(\omega_{(nn)}\), assuming here that for sufficiently large \(s\)

\[ \omega^{(s)}_{(nn)}\approx\omega_{(nn)}. \]

We shall estimate the degree of approximation of the successive \(\omega^{(s)}_{(nn)}\) to the desired \(\omega_{(nn)}\) by means of the numbers \(Ц^{(s)}\), where

\[ Ц^{(s)}=\sum_{j=1}^{n} Ц_j^{(s)}, \tag{24.s} \]

with

\[ Ц_j^{(s)}=\sum_{k=1}^{n}\left|a_{jk}^{(s)}\right|^2,\quad k\ne \begin{cases} j, & \text{if } a_{j,j+1}^{(s)}=0,\\ j\cap j+1, & \text{if } a_{j,j+1}^{(s)}. \end{cases} \tag{23.s} \]

An indication that the successive approximations \(\omega^{(s)}_{(nn)}\) tend without bound toward the desired \(\omega_{(nn)}\) will be the existence of the chain of inequalities

\[ Ц^{(0)}>Ц^{(1)}>Ц^{(2)}>\cdots>Ц^{(s)}>Ц^{(s+1)}>\cdots . \tag{25} \]

We shall consider that our computation of the matrix \(\omega_{(nn)}\) may be completed at that approximation \(\omega^{(s+1)}_{(nn)}\) for which

\[ Ц^{(s)}-Ц^{(s+1)}\leq \Delta, \tag{26} \]

where \(\Delta\) is the prescribed accuracy of the computation. If we further assume that the random errors \(\varepsilon^{(s)}_{\chi\lambda}\) in the components \(\omega^{(s)}_{\chi\lambda}\) of the matrices \(\omega^{(s)}_{(nn)}\) obey the Gaussian law, and denote the mean value \(C\varepsilon_{\chi\lambda}^{2}\) by \(\varepsilon^{2}\), then we shall find...

\[ \Delta^2 \simeq C \sum_{\chi,\lambda=1}^{n} \varepsilon_{\chi\lambda}^2 = \sum_{\chi,\lambda=1}^{n} C \varepsilon_{\chi\lambda}^2 = \sum_{\chi,\lambda=1}^{n} 1_{\chi\lambda}\varepsilon^2 = n^2\varepsilon^2 . \tag{27} \]

Hence, from the error \(\Delta\) computed according to (27), one can conversely find the root-mean-square error \(\pm \varepsilon\) in \(\omega_{\chi\lambda}^{(s)}\):

\[ \varepsilon \simeq \pm \frac{\Delta}{n}. \tag{28} \]

After we have obtained, with the intended degree of accuracy \(\Delta \leq \varepsilon\), the simplified matrix \(\omega_{(nn)}\), determined by the transformation (12)

\[ \omega_{(nn)}=\tilde{\mathfrak{h}}_{(nn)}a_{(nn)}\tilde{g}_{(nn)}, \tag{12} \]

we proceed to the calculation of the corresponding transforming matrix \(\tilde{g}_{(nn)}\). This can be done in two ways:

a) starting from the limiting relation

\[ \tilde{g}_{(nn)}=\tilde{g}_{(nn)}^{(0)}\tilde{g}_{(nn)}^{(1)}\ldots \tilde{g}_{(nn)}^{(\nu)} =\prod_{s=0}^{\nu}\tilde{g}_{(nn)}^{(s)}, \tag{29} \]

b) solving, with respect to the matrix \(g_{(nn)}\), the equation following from (12), for the known matrices \(a_{(nn)}\) and \(\omega_{(nn)}\),

\[ a_{(nn)}g_{(nn)}=g_{(nn)}\omega_{(nn)}. \tag{12a} \]

Which of these two ways of determining the matrix \(g_{(nn)}\) will prove simpler is difficult to predict in advance.

1. In conclusion, we shall prove the convergence of the proposed method for solving the spectral problem (1) for an arbitrary matrix \(a_{(nn)}\), which reduces to establishing the chain of inequalities (25), written in the form

\[ Ц^{(s)} > Ц^{(s+1)}, \qquad (s=0,1,2,\ldots), \tag{25} \]

where the quality indices of the individual approximations entering here, \(Ц^{(s)}, Ц^{(s+1)}\), are computed according to (23.s), (24.s)

\[ \begin{gathered} 1)\quad Ц_j^{(s)}=\sum_{k=1}^{n}\left|a_{kj}^{(s)}\right|^2, \qquad k\ne \begin{cases} j, & \text{if } a_{j,j+1}^{(s)}=0,\\ j\cap j+1 & \text{if } a_{j,j+1}^{(s)}=1; \end{cases} \\ 3)\quad Ц^{(s)}=\sum_{j=1}^{n} Ц_j^{(s)} . \tag{30} \end{gathered} \]

\[ 2)\quad \left|a_{jk}^{(s)}\right|^2 = a_{jk}^{(s)}\bar a_{jk}^{(s)} = \left(\alpha_{jk}^{(s)}+ i\beta_{jk}^{(s)}\right) \left(\alpha_{jk}^{(s)}- i\beta_{jk}^{(s)}\right), \qquad i=\sqrt{-1}. \]

To prove the validity of the chain of inequalities (25), first of all note that the trace \(tr\,a_{(nn)}\) of the matrix \(a_{(nn)}\), determined by the expression

\[ tr\,a_{(nn)}=\sum_{\chi=1}^{n} a_{\chi\chi}, \tag{31} \]

does not change in the case of a transformation of the form (12)

\[ b_{(nn)}=s_{(nn)}^{-1}a_{(nn)}s_{(nn)}=\sigma_{(nn)}a_{(nn)}s_{(nn)}. \tag{32} \]

where \(s_{(nn)}\) is an arbitrary transforming matrix. What has been said follows from the fact that

\[ \begin{aligned} \operatorname{tr} b_{(nn)} &=\sum_{\chi=1}^{n} b_{\chi\chi} =\operatorname{tr}\bigl(s_{(nn)}^{-1}a_{(nn)}s_{(nn)}\bigr) =\sum_{\chi=1}^{n}\sum_{\mu=1}^{n}\sum_{\nu=1}^{n} \sigma_{\chi\mu}a_{\mu\nu}s_{\nu\chi} \\ &=\sum_{\mu=1}^{n}\sum_{\nu=1}^{n}a_{\mu\nu} \sum_{\chi=1}^{n}\sigma_{\chi\mu}s_{\nu\chi} =\sum_{\mu=1}^{n}\sum_{\nu=1}^{n}a_{\mu\nu}e_{\nu\mu} =\sum_{\nu=1}^{n}a_{\nu\nu}e_{\nu\nu} =\sum_{\nu=1}^{n}a_{\nu\nu} =\operatorname{tr}a_{(nn)}, \end{aligned} \tag{33} \]

where \(e_{\nu\mu}\) are the components of the unit matrix
\(e_{(nn)}=\sigma_{(nn)}s_{(nn)}=s_{(nn)}\), for which

\[ e_{\nu\mu}=\sum_{\chi=1}^{n}s_{\nu\chi}\sigma_{\chi\mu} = \begin{cases} +1, & \text{if } \mu=\nu,\\ 0, & \text{if } \mu\ne\nu. \end{cases} \tag{34} \]

Let us now extract from the matrix of the \(s\)-th approximation
\(a_{(nn)}^{(s)}=\omega_{(nn)}^{(s)}\) the partial matrix
\(a_{(mm)}^{(s)}=a_{(mm)}^{\gamma\delta\ldots\nu}\), whose elements
\(a_{\chi\mu}^{(s)}\) are situated at the intersection of the \(m\) rows
\(\chi=\gamma,\delta,\ldots,\nu\) and the \(m\) columns
\(\mu=\gamma,\delta,\ldots,\nu\) of the general matrix
\(a_{(nn)}^{(s)}=\omega_{(nn)}^{(s)}\). It is assumed here that, for the indicated
\(m\) rows of the general matrix \(a_{(nn)}^{(s)}\), the corresponding indices
\(L_{\gamma},L_{\delta},\ldots,L_{\nu}\) have been taken to be the largest among
all \(n\) indices \(L_j\) of the matrix \(a_{(nn)}^{(s)}\).

Next we construct the transforming matrix of the \((s+1)\)-st approximation
\(g_{(nn)}^{(s)}\), taking the unit matrix \(e_{(nn)}\) and assigning to \(m^2\)
of its elements \(e_{\chi\mu}\) the same values \(a_{\chi\mu}^{(s)}\) as in the
partial matrix composed above,
\(a_{(mm)}^{(s)}=a_{(mm)}^{\gamma\delta\ldots\nu}\). After this we recalculate
the obtained transforming matrix into the reduced matrix
\(\tilde g_{(nn)}^{(s)}\), whose columns \(\tilde g_{(n)\chi}^{(s)}\) satisfy the
condition \(\lvert \tilde g_{(n)\chi}^{(s)}\rvert=1\), and then find the
corresponding inverse reduced matrix
\((\tilde g_{(nn)}^{(s)})^{-1}=\tilde{\mathcal X}_{(nn)}^{(s)}\). Then the
\((s+1)\)-st approximation \(a_{(nn)}^{(s+1)}=\omega_{(nn)}^{(s+1)}\) to the
simplified matrix \(\omega_{(nn)}\) is determined by the double transformation of
the form (20)

\[ \omega_{(nn)}^{s+1} =(\tilde g_{(nn)}^{(s)})^{-1}\omega_{(nn)}^{(s)}\tilde g_{(nn)}^{(s)} =\tilde{\mathcal X}_{(nn)}^{(s)}a_{(nn)}^{(s)}\tilde g_{(nn)}^{(s)} =a_{(nn)}^{(s+1)} . \tag{20.s+1} \]

Let us now consider the trace
\(\operatorname{tr}\bigl[a_{(mm)}^{(s)}\bar a_{(mm)}^{(s)*}\bigr]\) of the matrix
\(\bigl[a_{(mm)}^{(s)}\bar a_{(mm)}^{(s)*}\bigr]\), where
\(a_{(mm)}^{(s)}=a_{(mm)}^{\gamma\delta\ldots\nu}\) is the partial matrix
constructed by the method described above from the general matrix
\(a_{(nn)}^{(s)}\) after the \(s\)-th approximation. At the same time, note that

\[ \begin{gathered} 1)\quad a_{(mm)}^{(s)}=\alpha_{(mm)}^{(s)}+i\beta_{(mm)}^{(s)},\qquad 2)\quad \bar a_{(mm)}^{(s)*}=\alpha_{(mm)}^{(s)*}-i\beta_{(mm)}^{(s)*},\\ 3)\quad a_{jk}^{(s)}=\alpha_{jk}^{(s)}+i\beta_{jk}^{(s)},\qquad 4)\quad \bar a_{kj}^{(s)*}=\alpha_{kj}^{(s)*}-i\beta_{kj}^{(s)*},\\ 5)\quad (\alpha_{jk}^{(s)})^*=\alpha_{kj}^{(s)*},\qquad (\beta_{jk}^{(s)})^*=\beta_{kj}^{(s)*};\qquad 6)\quad \operatorname{tr}\alpha_{(mm)}^{(s)}=\sum_{j=1}^{m}a_{jj}. \end{gathered} \tag{35} \]

Then, taking into account the remarks made, we find that

\[ \operatorname{tr}\bigl[a_{(mm)}^{(s)}\bar a_{(mm)}^{(s)*}\bigr] = \sum_{\chi=\gamma,\delta,\ldots,\nu} \left[ a_{\gamma\chi}^{(s)}a_{\chi\gamma}^{(s)*} +a_{\delta\chi}^{(s)}a_{\chi\delta}^{(s)*} +\cdots+ a_{\nu\chi}^{(s)}a_{\chi\nu}^{(s)*} \right] = \tag{36} \]

\[ = \lvert a_{\gamma\gamma}^{(s)}\rvert^2 +\lvert a_{\delta\delta}^{(s)}\rvert^2 +\cdots+ \lvert a_{\nu\nu}^{(s)}\rvert^2 + \sum_{\chi=\gamma,\delta,\ldots,\nu} \left[ \lvert a_{\gamma\chi}^{(s)}\rvert^2_{\chi\ne\gamma} + \lvert a_{\delta\chi}^{(s)}\rvert^2_{\chi\ne\delta} +\cdots+ \lvert a_{\nu\chi}^{(s)}\rvert^2_{\chi\ne\nu} \right]. \]

Let us next consider the trace \(\operatorname{tr}[a^{(s)}_{(nn)}\bar a^{(s)*}_{(nn)}]\) of the matrix \([a^{(s)}_{(nn)}\bar a^{(s)*}_{(nn)}]\), where \(a^{(s)}_{(nn)}=\omega^{(s)}_{(nn)}\) is the \(s\)-th approximation to the simplified matrix \(\omega_{(nn)}\), obtained by a double transformation of the form (12). First of all, taking (23.5) and (24.5) into account, we find that

\[ \operatorname{tr}[a^{(s)}_{(nn)}\bar a^{(s)*}_{(nn)}] = \sum_{j,\varkappa=1}^{n} a^{(s)}_{j\varkappa}\bar a^{(s)*}_{\varkappa j} = \sum_{j=1}^{n}|a^{(s)}_{jj}|^{2} + \sum_{j,\varkappa=1}^{n}|a^{(s)}_{j\varkappa}|^{2} = \]

\[ = \sum_{j=1}^{n}|a^{(s)}_{jj}|^{2} - L^{(s)}+\Delta^{(s)}, \tag{37} \]

where \(\Delta^{(s)}=0\) if all eigenvalues \(\lambda_i^{(s)}\) of the matrix \(a^{(s)}_{(nn)}\) are distinct, and \(\Delta^{(s)}>0\) if some of the values \(\lambda_i^{(s)}\) are multiple.

Let us write the expanded expression for the first term in equality (37), taking into account representation (36) for \(\operatorname{tr}[a^{(s)}_{(nn)}\bar a^{(s)*}_{(nn)}]\). Then we shall find that

\[ \sum_{j=1}^{n}|a^{(s)}_{jj}|^{2} = \sum_{\substack{j=1\\ j\ne\gamma,\delta,\ldots,\nu}}^{n}|a^{(s)}_{jj}|^{2} + \left[ |a^{(s)}_{\gamma\gamma}|^{2} + |a^{(s)}_{\delta\delta}|^{2} +\cdots+ |a^{(s)}_{\nu\nu}|^{2} \right] = \tag{*} \]

\[ = \sum_{\substack{j=1\\ j\ne\gamma,\delta,\ldots,\nu}}^{n}|a^{(s)}_{jj}|^{2} + \operatorname{tr}[a^{(s)}_{(mm)}\bar a^{(s)*}_{(mm)}] - \sum_{\varkappa=\gamma,\delta,\ldots,\nu} \left[ |a^{(s)}_{\gamma\varkappa}|^{2}_{\varkappa\ne\gamma} + |a^{(s)}_{\delta\varkappa}|^{2}_{\varkappa\ne\delta} +\cdots+ |a^{(s)}_{\nu\varkappa}|^{2}_{\varkappa\ne\nu} \right]. \]

It follows from this that

\[ \operatorname{tr}[a^{(s)}_{(nn)}\bar a^{(s)*}_{(nn)}] = L^{(s)} + \sum_{\substack{j=1\\ j\ne\gamma,\delta,\ldots,\nu}}^{n}|a^{(s)}_{jj}|^{2} + \operatorname{tr}[a^{(s)}_{(mm)}\bar a^{(s)*}_{(mm)}] - \tag{38.5} \]

\[ - \sum_{\varkappa=\gamma,\delta,\ldots,\nu} \left[ |a^{(s)}_{\gamma\varkappa}|^{2}_{\varkappa\ne\gamma} + |a^{(s)}_{\delta\varkappa}|^{2}_{\varkappa\ne\delta} +\cdots+ |a^{(s)}_{\nu\varkappa}|^{2}_{\varkappa\ne\nu} \right] + \Delta^{(s)}. \]

In exactly the same way, for the matrix of the \((s+1)\)-st approximation \(a^{(s+1)}_{(nn)}=\omega^{(s+1)}_{(nn)}\), determined according to \((20.s+1)\), we find

\[ \operatorname{tr}[a^{(s+1)}_{(nn)}\bar a^{(s+1)*}_{(nn)}] = L^{(s+1)} + \sum_{\substack{j=1\\ j\ne\gamma,\delta,\ldots,\nu}}^{n}|a^{(s+1)}_{jj}|^{2} + \operatorname{tr}[a^{(s+1)}_{(mm)}\bar a^{(s+1)*}_{(mm)}] - \]

\[ - \sum_{\varkappa=\gamma,\delta,\ldots,\nu} \left[ |a^{(s+1)}_{\gamma\varkappa}|^{2}_{\varkappa\ne\gamma} + |a^{(s+1)}_{\delta\varkappa}|^{2}_{\varkappa\ne\delta} +\cdots+ |a^{(s+1)}_{\nu\varkappa}|^{2}_{\varkappa\ne\nu} \right] + \Delta^{(s+1)}. \tag{38.5+1} \]

Here it has been taken into account that, after carrying out the \(s\)-th approximation, we singled out a certain partial matrix \(a^{(s)}_{(mm)}\), which was then used to construct the reduced transforming matrix \(\tilde g^{(s)}_{(nn)}\) entering into the double transformation \((20.s+1)\). Therefore, the partial matrix \(a^{(s+1)}_{(mm)}\), with components \(a^{(s+1)}_{\varkappa\lambda}\), contains the same rows \(\varkappa=\gamma,\delta,\ldots,\nu\) and the same columns \(\lambda=\gamma,\delta,\ldots,\nu\) as the matrix \(a^{(s)}_{(mm)}=a^{\gamma\delta\ldots\nu}_{(m)}\). As for the matrix \(a^{(s+1)}_{(nn)}\), it naturally contains the same \(n\) rows and \(n\) columns as the matrix \(a^{(s)}_{(nn)}\).

1. From comparison of equalities \((38.s)\) and \((38.s+1)\), the convergence of the proposed method is still not apparent, since

\[ \operatorname{tr}\!\left[a_{(nn)}^{(s+1)}\bar a_{(nn)}^{(s+1)*}\right] =\operatorname{tr}\!\left[\left(\widetilde{\mathcal X}_{(nn)}^{(s)}a_{(nn)}^{(s)}\bar g_{(nn)}^{(s)}\right) \left(\widetilde{\mathcal X}_{(nn)}^{(s)}a_{(nn)}^{(s)}\bar g_{(nn)}^{(s)}\right)^*\right]= \]
\[ =\operatorname{tr}\!\left[\widetilde{\mathcal X}_{(nn)}^{(s)}a_{(nn)}^{(s)}\bar g_{(nn)}^{(s)}\bar g_{(nn)}^{(s)*}\bar a_{(nn)}^{(s)*} \widetilde{\mathcal X}_{(nn)}^{(s)*}\right]\ne \operatorname{tr}\!\left[\widetilde{\mathcal X}_{(nn)}^{(s)} \left(a_{(nn)}^{(s)}\bar a_{(nn)}^{(s)*}\right) \left(\widetilde{\mathcal X}_{(nn)}^{(s)}\right)^{-1}\right]= \]
\[ =\operatorname{tr}\!\left[\widetilde{\mathcal X}_{(nn)}^{(s)} \left(a_{(nn)}^{(s)}\bar a_{(nn)}^{(s)*}\right)\bar g_{(nn)}^{(s)}\right] =\operatorname{tr}\!\left[a_{(nn)}^{(s)}\bar a_{(nn)}^{(s)}\right], \]

where the sign \(\ne\) has so far been inserted on purely external grounds. Therefore we shall modify our method somewhat in order to obtain a simpler proof of its convergence.

Let us decompose the given matrix \(a_{(nn)}\) of arbitrary form into a Hermitian matrix \(b_{(nn)}\) and a skew-Hermitian matrix \(c_{(nn)}\), taking

\[ 1)\quad b_{(nn)}=\frac12\left(a_{(nn)}+\bar a_{(nn)}^*\right),\qquad 2)\quad c_{(nn)}=\frac12\left(a_{(nn)}-\bar a_{(nn)}^*\right), \]
\[ 3)\quad a_{(nn)}=\frac12\left(b_{(nn)}+c_{(nn)}\right). \tag{39} \]

Consequently,

\[ 1)\quad b_{(nn)}=\bar b_{(nn)}^*,\qquad 2)\quad c_{(nn)}=-\bar c_{(nn)}^*;\qquad 3)\quad \operatorname{tr}c_{(nn)}=-\operatorname{tr}\bar c_{(nn)}^*=0_{(nn)}; \tag{40} \]
\[ 4)\quad a_{(nn)}\bar a_{(nn)}^* =\frac14\left[(b_{(nn)}+c_{(nn)})(\bar b_{(nn)}^*-\bar c_{(nn)}^*)\right] =\frac14\left(b_{(nn)}\bar b_{(nn)}^*-c_{(nn)}\bar c_{(nn)}^*\right); \]
\[ 5)\quad \operatorname{tr}\left(a_{(nn)}\bar a_{(nn)}^*\right) =\frac14\operatorname{tr}\left(b_{(nn)}\bar b_{(nn)}^*-c_{(nn)}\bar c_{(nn)}^*\right)= \]
\[ =\frac14\left[\operatorname{tr}\left(b_{(nn)}\bar b_{(nn)}^*\right) -\operatorname{tr}\left(c_{(nn)}\bar c_{(nn)}^*\right)\right]; \]
\[ 6)\quad b_{(nn)}^{(s+1)} =(\bar u_{(nn)}^{(s)})^{-1}b_{(nn)}^{(s)}\bar u_{(nn)}^{(s)} =\widetilde\eta_{(nn)}^{(s)}b_{(nn)}^{(s)}\bar u_{(nn)}^{(s)}, \]
\[ 7)\quad c_{(nn)}^{(s+1)} =(\bar w_{(nn)}^{(s)})^{-1}c_{(nn)}^{(s)}\bar w_{(nn)}^{(s)} =\widetilde\beta_{(nn)}^{(s)}c_{(nn)}^{(s)}\bar w_{(nn)}^{(s)}. \]

Let us consider the relations (40.6) and (40.7) in more detail.

Turning first to the double transformation (40.6) and noting that here \(b_{(nn)}^{(s)*}=\bar b_{(nn)}^{(s)}\), we obtain

\[ 1)\quad b_{(nn)}^{(s+1)} =\widetilde\eta_{(nn)}^{(s)}b_{(nn)}^{(s)}\bar u_{(nn)}^{(s)} =\widetilde\eta_{(nn)}^{(s)}\bar b_{(nn)}^{(s)*}\bar u_{(nn)}^{(s)}, \]
\[ 2)\quad \bar b_{(nn)}^{(s+1)*} =\bar u_{(nn)}^{(s)*}\bar b_{(nn)}^{(s)*}\widetilde{\bar\eta}_{(nn)}^{(s)*} =\bar u_{(nn)}^{(s)*}b_{(nn)}^{(s)}\widetilde{\bar\eta}_{(nn)}^{(s)*}. \tag{**} \]

It follows from this that, if we require that \(b_{(nn)}^{(s+1)}=\bar b_{(nn)}^{(s+1)*}\), then from \((**)\) we find

\[ 1)\quad \widetilde\eta_{(nn)}^{(s)}=(\bar u_{(nn)}^{(s)})^{-1}=\bar u_{(nn)}^{(s)*},\qquad 2)\quad \bar u_{(nn)}^{(s)}\bar u_{(nn)}^{(s)}=e_{(nn)}, \tag{41} \]

and this means that \(\bar u_{(nn)}^{(s)}\) is a unitary matrix. Therefore then

\[ \operatorname{tr}\!\left[b_{(nn)}^{(s+1)}\bar b_{(nn)}^{(s+1)*}\right] =\operatorname{tr}\!\left[\widetilde\eta_{(nn)}^{(s)}b_{(nn)}^{(s)} \left(\bar u_{(nn)}^{(s)}\bar u_{(nn)}^{(s)*}\right) \bar b_{(nn)}^{(s)*}\widetilde{\bar\eta}_{(nn)}^{(s)*}\right]= \]
\[ =\operatorname{tr}\!\left[\widetilde\eta_{(nn)}^{(s)} \left(b_{(nn)}^{(s)}\bar b_{(nn)}^{(s)*}\right)\bar u_{(nn)}^{(s)}\right] =\operatorname{tr}\!\left[b_{(nn)}^{(s)}\bar b_{(nn)}^{(s)*}\right]. \tag{42} \]

Turning next to the double transformation (40.7) and observing that here \(c_{(nn)}^{(s)*}=-\bar c_{(nn)}^{(s)}\), we obtain

\[ \begin{aligned} 1)\quad c_{(nn)}^{(s+1)}&=\bar{\beta}_{(nn)}^{(s)}c_{(nn)}^{(s)}\bar{\omega}_{(nn)}^{(s)} =-\beta_{(nn)}^{(s)}\bar{c}_{(nn)}^{(s)*}\tilde{\omega}_{(nn)}^{(s)},\\ 2)\quad \bar{c}_{(nn)}^{(s+1)}&=-\bar{\omega}_{(nn)}^{(s)}c_{(nn)}^{(s)*}\bar{\beta}_{(nn)}^{(s)} =-\bar{\omega}_{(nn)}^{(s)}c_{(nn)}^{(s)}\bar{\beta}_{(nn)}^{(s)*}. \end{aligned} \tag{***} \]

Consequently, if we require that \(c_{(nn)}^{(s+1)}=-\bar{c}_{(nn)}^{(s+1)*}\), then from \((***)\) we obtain

\[ 1)\quad \bar{\beta}_{(nn)}^{(s)}=(\tilde{\omega}_{(nn)}^{(s)})^{-1} =-\bar{\omega}_{(nn)}^{(s)*}, \qquad 2)\quad \bar{\omega}_{(nn)}^{(s)*}\tilde{\omega}_{(nn)}^{(s)}=-e_{(nn)}. \tag{43} \]

It follows from this that

\[ \operatorname{tr}\left[c_{(nn)}^{(s+1)}\bar{c}_{(nn)}^{(s+1)*}\right] =\operatorname{tr}\left[\bar{\beta}_{(nn)}^{(s)}c_{(nn)}^{(s)} \left(\tilde{\omega}_{(nn)}^{(s)}\bar{\omega}_{(nn)}^{(s)*}\right) \bar{c}_{(nn)}^{(s)*}\bar{\beta}_{(nn)}^{(s)*}\right] = \]

\[ =\operatorname{tr}\left[\bar{\beta}_{(nn)}^{(s)} \left(c_{(nn)}^{(s)}\bar{c}_{(nn)}^{(s)*}\right) \tilde{\omega}_{(nn)}^{(s)}\right] =\operatorname{tr}\left[c_{(nn)}^{(s)}\bar{c}_{(nn)}^{(s)*}\right]. \tag{44} \]

Finally comparing (42) and (44) with (40.5), we find, for the matrices \(a_{(rr)}^{(s)}\) and \(a_{(rr)}^{(s+1)}\) entering into \((38.s)\) and \((38.s+1)\), the following general relation for \(r=m,n\):

\[ \operatorname{tr}\left[a_{(rr)}^{(s+1)}\bar{a}_{(rr)}^{(s+1)*}\right] = \operatorname{tr}\left[a_{(rr)}^{(s)}\bar{a}_{(rr)}^{(s)*}\right], \qquad (r=m,n). \tag{45} \]

In addition, taking into account the special structure (19) of the matrices \(\tilde{g}_{(nn)}^{(s)}\) and \(\tilde{\varkappa}_{(nn)}^{(s)}\) in the double transformation \((20.s+1)\), we establish the existence of additional relations

\[ 1)\quad a_{ij}^{(s)}=a_{jj}^{(s+1)},\quad \text{if } j\ne\gamma,\delta,\ldots,\nu; \qquad 2)\quad \sum_{\substack{i=1\\ i=\gamma,\delta,\ldots,\nu}}^{n}\left|a_{ij}^{(s)}\right|^{2} = \sum_{j=1}^{n}\left|a_{jj}^{(s+1)}\right|^{2}. \tag{46} \]

Now comparing the equalities \((38.s)\) and \((38.s+1)\), with account taken of relations (45), (46), we arrive at the conclusion that

\[ Ц^{(s+1)}=Ц^{(s)} - S_{\varkappa=\gamma,\delta,\ldots,\nu} \left[ \left(\left|a_{\gamma\varkappa}^{(s)}\right|^{2} -\left|a_{\gamma\varkappa}^{(s+1)}\right|^{2}\right) + \left(\left|a_{\delta\varkappa}^{(s)}\right|^{2} -\left|a_{\delta\varkappa}^{(s+1)}\right|^{2}\right) +\right. \]

\[ \left. +\cdots+ \left(\left|a_{\nu\varkappa}^{(s)}\right|^{2} -\left|a_{\nu\varkappa}^{(s+1)}\right|^{2}\right) \right], \tag{47} \]

since \(\Delta^{(s)}=\Delta^{(s+1)}\). But we construct the transforming matrices \(\bar{g}_{(nn)}^{(s)}\) in such a way that the matrix transformed according to \((20.s+1)\),

\[ a_{(nn)}^{(s+1)}=\omega_{(nn)}^{(s+1)}, \]

satisfies the conditions

\[ a_{\varkappa\mu}^{(s+1)}=0,\quad \text{if } \varkappa,\mu=\gamma,\delta,\ldots,\nu \cap\left[(\varkappa\ne\mu)\cup(\varkappa\ne\mu\cap\mu+1)\right]. \tag{48} \]

Therefore equality (47) assumes the following final form:

\[ Ц^{(s+1)}=Ц^{(s)} - S_{\varkappa=\gamma,\delta,\ldots,\nu} \left[ \left|a_{\gamma\varkappa}^{(s)}\right|^{2} + \left|a_{\delta\varkappa}^{(s)}\right|^{2} +\cdots+ \left|a_{\nu\varkappa}^{(s)}\right|^{2} \right], \tag{47.1} \]

whence it follows that, indeed,

\[ Ц^{(s+1)}<Ц^{(s)},\qquad (s=0,1,2,\ldots). \tag{25} \]

Consequently, the proposed method for solving the spectral problem for an arbitrary matrix \(a_{(nn)}\) always converges. Equality

(48.1) also shows that the higher the order \(mm\) of the auxiliary matrix \(a^{(s)}_{(mm)}=a^{r_0,\ldots}_{(mm)}\), the faster the sequence of matrices \(a^{(s)}_{(nn)}=\omega^{(s)}_{(nn)}\) approaches the simplified matrix \(\omega_{(nn)}\).

1. The spectral problem for an arbitrary matrix \(a_{(nn)}\) can also be solved in another way, used in proving the convergence of the proposed method, namely: by expressing the given matrix \(a_{(nn)}\) through the corresponding Hermitian \(b_{(nn)}\) and skew-Hermitian \(c_{(nn)}\) matrices

\[ \begin{aligned} &1)\quad b_{(nn)}=\frac{1}{2}\left(a_{(nn)}+\bar a^{*}_{(nn)}\right),\qquad 2)\quad c_{(nn)}=\frac{1}{2}\left(a_{(nn)}-\bar a^{*}_{(nn)}\right), \tag{49}\\ &3)\quad a_{(nn)}=\frac{1}{2}\left(b_{(nn)}+c_{(nn)}\right). \end{aligned} \]

Then we solve two particular spectral problems,

\[ 1)\quad \left(b_{(nn)}-\mu e_{(nn)}\right)u_{(n1)}=0_{(n1)},\qquad 2)\quad \left(c_{(nn)}-\nu e_{(nn)}\right)w_{(n1)}=0_{(n1)} \tag{50} \]

by the method described above, that is, relying extensively here on Danilevsky’s method. In this case the determination of the inverse transforming matrices \(\tilde\eta_{(nn)}\) and \(\tilde\beta_{(nn)}\) is substantially simplified, since, according to (41) and (43),

\[ \begin{aligned} &1)\quad \tilde\eta^{(s)}_{(nn)}=\bar{\tilde u}^{(s)*}_{(nn)},\qquad 3)\quad \tilde\beta^{(s)}_{(nn)}=-\bar{\tilde w}^{(s)*}_{(nn)}, \tag{51}\\ &2)\quad \tilde u^{(s)}_{(nn)}\bar{\tilde u}^{(s)*}_{(nn)}=e_{(nn)},\qquad 4)\quad \tilde w^{(s)}_{(nn)}\bar{\tilde w}^{(s)*}_{(nn)}=-e_{(nn)}. \end{aligned} \]

REFERENCES

1. A. G. Kurosh. A Course of Higher Algebra. Moscow, Fizmatgiz, 1962.
2. D. K. Faddeev and V. N. Faddeeva. Computational Methods of Linear Algebra. Moscow–Leningrad, Fizmatgiz, 1963.
3. V. V. Voevodin. Numerical Methods of Algebra. Moscow, “Nauka,” 1966.