Permuted Graph Matrices and Their Applications

A permuted graph matrix is a matrix $$V \in \mathbb{C}^{(m+n)\times m}$$ such that every row of the m × m identity matrix I m appears at least once as a row of V. Permuted graph matrices can be used in some contexts in place of orthogonal matrices, for instance when giving a basis for a subspace $$\mathcal{U}\subseteq \mathbb{C}^{m+n}$$ , or to normalize matrix pencils in a suitable sense. In these applications the permuted graph matrix can be chosen with bounded entries, which is useful for stability reasons; several algorithms can be formulated with numerical advantage with permuted graph matrices. We present the basic theory and review some applications from optimization or in control theory.