Approximating orthogonal matrices by permutation matrices

Simple item page
dc.creatorBarvinok, Alexander
dc.date2005-10-27
dc.date.accessioned2026-07-07T06:48:02Z
dc.date.available2026-07-07T06:48:02Z
dc.descriptionMotivated in part by a problem of combinatorial optimization and in part by analogies with quantum computations, we consider approximations of orthogonal matrices U by ``non-commutative convex combinations'' A of permutation matrices of the type A=sum A_sigma sigma, where sigma are permutation matrices and A_sigma are positive semidefinite nxn matrices summing up to the identity matrix. We prove that for every nxn orthogonal matrix U there is a non-commutative convex combination A of permutation matrices which approximates U entry-wise within an error of c n^{-1/2}ln n and in the Frobenius norm within an error of c ln n. The proof uses a certain procedure of randomized rounding of an orthogonal matrix to a permutation matrix.
dc.description18 pages
dc.identifierhttps://arxiv.org/abs/math/0510612
dc.identifierhttp://arxiv.org/abs/math/0510612
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/103850
dc.subjectFunctional Analysis
dc.subjectMetric Geometry
dc.subject05A05, 52A20, 52A21, 46B09, 15A48, 15A60
dc.titleApproximating orthogonal matrices by permutation matrices
dc.typetext

Files

Collections

arXiv