Computing the closest real normal matrix and normal completion

In this article, we consider the problems (unsolved in the literature) of computing the nearest normal matrix X to a given non-normal matrix A, under certain constraints, that are (i) if A is real, we impose that also X is real; (ii) if A has known entries on a given sparsity pattern Ω and unknown/uncertain entries otherwise, we impose to X the constraint xij = aij for all entries (i,j) in the pattern Ω. As far as we know, there do not exist in the literature specific algorithms aiming to solve these problems. For the case in which all entries of A can be modified, there exists an algorithm by Ruhe, which is able to compute the closest normal matrix. However, if A is real, the closest computed matrix by Ruhe’s algorithm might be complex, which motivates the development of a different algorithm preserving reality. Normality is characterized in a very large number of ways; in this article, we consider the property that the square of the Frobenius norm of a normal matrix is equal to the sum of the squares of the moduli of its eigenvalues. This characterization allows us to formulate as equivalent problem the minimization of a functional of an unknown matrix, which should be normal, fulfill the required constraints, and have minimal distance from the given matrix A.