## 6 Modified Unitary R-D Root MUSIC
while\(k\leq K\)and\(\|\mathbf{v}_{k}-\mathbf{v}_{k-1}\|^{2}>tol\)do
2\(\mathbf{v}_{k+1}\leftarrow\mathbf{C}\mathbf{v}_{k}\)\(\mathbf{v}_{k+1}\leftarrow\dfrac{\mathbf{v}_{k+1}}{\|\mathbf{v}_{k+1}\|}\)\(k\gets k+1\)
3 end while
4 if\(k>K\)then /* Convergence failed */ return\(NULL\)
5 end if
6 else /* Convergence succeeded */ return\(\mathbf{v}_{k}\)
7 end while
```  
**Algorithm 2**Power Method  
The companion matrix of the polynomial \(p(z)\) is defined in Equation (47) [43],  
\[\mathbf{P}\triangleq \begin{bmatrix}0&1&0&\ldots&0\\ 0&0&1&\ldots&0\\ 0&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\ddots&0&1\\ -c_{0}&-c_{1}&\ldots&-c_{2M-4}&-c_{2M-3}\end{bmatrix} \in\mathbb{C}^{(2M-2) \times(2M-2)}, \tag{47}\]  
where \(c_{i}=a_{i}/a_{2M-2}\forall i=0,1,\ldots,2M-2\). That is, the companion matrix by definition relates to a polynomial in which its highest degree coefficient is one (\(a_{2M-2}=1\)), that is the reason we have to divide all coefficients by \(a_{2M-2}\) as indicated by Equation (48),  
\[\dfrac{p(z)}{a_{2M-2}}=\dfrac{a_{0}}{a_{2M-2}}+\dfrac{a_{1}}{a_{2M-2}}z+\cdots +\dfrac{a_{2M-2}}{a_{2M-2}}z^{2M-2}=c_{0}+c_{1}z+\cdots+z^{2M-2}. \tag{48}\]  
The matrix \(\mathbf{P}\) is in a complex domain, but the implemented solution executes the Shifted QR Algorithm for real-valued matrices only. To circumvent this problem, that algorithm solves the complex EVD via equivalent real formulation by converting the complex-valued companion matrix into a real-valued one. That is, the \((2M-2)\times(2M-2)\) complex eigenvalue problem in Equation (49),  
\[(\mathrm{Re}(\mathbf{P})+j\mathrm{Im}(\mathbf{P}))\cdot(\mathbf{u}+j\mathbf{v })=\lambda(\mathbf{u}+j\mathbf{v}) \tag{49}\]  
can be reformulated as \((4M-4)\times(4M-4)\) real matrix problem in accordance with Equation (50) [47],  
\[\underbrace{ \begin{bmatrix}\mathrm{Re}(\mathbf{P})&-\mathrm{Im}(\mathbf{P})\\ \mathrm{Im}(\mathbf{P})&\mathrm{Re}(\mathbf{P})\\ \mathrm{Pr}_{\mathbf{S}}\end{bmatrix} }_{\mathbf{P}_{\mathbf{S}}}\cdot \begin{bmatrix} \mathbf{u}\\ \mathbf{v}\end{bmatrix} =\lambda \begin{bmatrix}\mathbf{u}\\ \mathbf{v}\end{bmatrix} . \tag{50}\]However, the eigenvalue (\(\lambda\)) could still be a complex number since the matrix in problem (50) is non-symmetric ([33], pp. 486-487). That would apparently require complex arithmetic, but the implemented Shifted QR Algorithm circumvents it. Refer to [33] for more detail. The eigenvalue decomposition of \(\mathbf{P}_{R}\) in the reformulated problem (Equation (50)) outputs two times the number of eigenvalues of \(\mathbf{P}\) and the complex-valued ones come in pairs of \((\lambda,\overline{\lambda})\) since \(\mathbf{P}_{R}\) is a real matrix [46; 48]. The implemented solution can easily detect which one, \(\lambda\) or \(\overline{\lambda}\), is the eigenvalue of \(\mathbf{P}\) by verifying which is the root of the polynomial \(p(z)\). Moreover, the EVD of \(\mathbf{P}_{R}\) will increase the computations since its size is two times greater than \(\mathbf{P}\), but since the number of antennas (\(M\)) is small for an ULA in IoT devices, we can afford this small overburden, especially because the elimination of complex arithmetic could partly or even totally compensate this computational increment. However, before executing the Shifted QR Algorithm the implemented solution applies the balancing technique, and afterward, it reduces the matrix to Hessenberg form. Both algorithms are an adaptation of [33] for the implemented solution. The balancing technique is a method to reduce the rounding error sensitivity of eigenvalues during the execution of EVD. Hessenberg decomposition transforms a matrix into a simpler one (Hessenberg form) to speed up the execution time of the Shifted QR Algorithms. Algorithm 3 outputs \(4M-4\) eigenvalues in which \(2M-2\) are the roots of the polynomial \(p(z)\), and the other \(2M-2\) are not roots but the complex conjugate of the cited eigenvalues, as explained previously.