Approximating orthogonal matrices by permutation matrices

Details Approximating orthogonal matrices by permutation matrices Approximating orthogonal matrices by permutation matrices

2005-10-27

arxiv.org/abs/math/0510612v1

Mathematics

Functional Analysis

18 pages

Scientific paper

Motivated 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.

Affiliated with

Also associated with

No associations

Rating

Approximating orthogonal matrices by permutation matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating orthogonal matrices by permutation matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating orthogonal matrices by permutation matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-322951