Computing the optimal commuting matrix pairs (Q678226)

If \(A\) and \(B\) are commuting matrices (\(AB=BA\)), then they can be simultaneously diagonalized. From their eigenvalues, the azimuth/elevation directions of arrival in an array signal processing application can be computed. When \(A\) and \(B\) are contaminated with noise, the commuting property is lost in general and minimal perturbations are to be found restoring the commuting property. In this paper, only \(B\) is assumed to be perturbed and a matrix \(X\) of minimal Frobenius norm is constructed such that \(A(B+X)=(B+X)A\). Stacking the columns of \(X\) and \(B\) in vectors \(x\) and \(b\) respectively, the problem can be formulated as \(Sx=-Sb\) where \(S=I\otimes A-A^T\otimes I\). The matrix \(S\) is of size \(n^2\times n^2\), but it is sparse and structured. This paper describes an algorithm which reduces the work to \(O(n^5)\). It can be further reduced to \(O(n^4)\), but unfortunately, then the algorithm becomes unstable in general. However, it is shown that for the signal processing problem mentioned above, the algorithm is still adequate.