Computational geometry of positive definiteness (Q445814)

Let \({\mathcal V}\) denote a real subspace of \({\mathbb C}^{n\times n}\) consisting of Hermitian matrices. The authors address the problem of determining if \({\mathcal V}\) possesses a positive definite element. Given an orthonormal basis \(V_1,\dots,V_k\) of \({\mathcal V}\), the joint numerical range is defined as the set of all points \((x^\ast V_1x,\dots,x^\ast V_kx)\) in \({\mathbb R}^k\) with \(x\in{\mathbb C}^n\) of unit length. It is shown that \({\mathcal V}\) possesses positive definite elements if and only if the joint numerical range is contained within a half-space that does not contain the origin. Moreover, for any hyperplane through the origin in \({\mathbb R}^k\) with unit normal vector \(u=(u_1,\dots,u_k)\), one can find a point \(p\) on the boundary of the joint numerical range whose distance along \(u\) from the hyperplane is the smallest eigenvalue \(\lambda\) of \(V=u_1V_1+\dots+u_kV_k\). In particular, \(V\) is positive definite if \(\lambda>0\). This geometric connection between positive definite elements of \({\mathcal V}\) and the joint numerical range is exploited by the authors to construct computational-geometric algorithms for finding a positive definite element: one using a perceptron algorithm, and two others using ellipsoid methods. These algorithms are then compared by means of numerical experiments.