<blockquote>
  <p><strong>Theorem.</strong> <em>The problem in the post is NP-hard, by reduction from Subset-Sum.</em></p>
</blockquote>

<p>Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op.</p>

<hr>

<p>Here is the intuition.  The problem in the post is</p>

<ul>
<li><em>Is there a permutation matrix in the span of a given set of matrices?</em></li>
</ul>

<p>This is essentially the same as</p>

<ul>
<li><em>Is there a permutation matrix that (thinking of the matrix as a vector) satisfies some given linear constraints?</em></li>
</ul>

<p>This in turn is the same as</p>

<ul>
<li><em>Is there a perfect matching (in a complete bipartite graph) whose incidence vector satisfies some given linear constraints?</em> </li>
</ul>

<p>Reducing Subset-Sum to the latter problem is a standard exercise.</p>

<p>Here is the detailed proof.</p>

<hr>

<p>Define the following intermediate problem:</p>

<blockquote>
  <p><strong>Matching-Sum:</strong></p>
  
  <p><strong>input:</strong> <em>Complete, bipartite graph $G=(U,V,E)$ with non-negative
  integer edge weights, and non-negative integer target $T$.</em></p>
  
  <p><strong>output:</strong> <em>Does $G$ contain a perfect matching of weight exactly $T$?</em></p>
</blockquote>

<hr>

<blockquote>
  <p><strong>Lemma 1</strong>. <em>Subset-Sum poly-time reduces to Matching-Sum.</em></p>
</blockquote>

<p>Proving this is a standard homework exercise.  The proof is at the end.</p>

<blockquote>
  <p><strong>Lemma 2.</strong> <em>Matching-Sum poly-time reduces to the problem in the post.</em></p>
</blockquote>

<p><em>Proof of Lemma 2.</em> Fix a Matching-Sum input: a complete bipartite graph $G=(U,V,E)$ with non-negative integer edge weights $w:U\times V\rightarrow \mathbb{N}_+$, and target $T\in \mathbb{N}_+$, where $U=\{u_1,\ldots,u_n\}$ and $V=\{v_1, \ldots, v_n\}$. For each $i,j\in\{1,2,\ldots,n\}$, define $M^{(ij)}$ to be the matrix in $\mathbb{R}^{(n+1)\times (n+1)}$ where $M^{(ij)}_{ij} = T$, and $M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$, and all other entries are zero.  The reduction outputs the following set of matrices:
$$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$$
This defines the reduction.</p>

<p><strong>Claim.</strong> <em>The span of this set of matrices consists of
those matrices $M \in\mathbb{R}^{(n+1)\times(n+1)}$ satisfying
the linear constraints $M_{h,n+1} = M_{n+1,h} = 0$ for all $h\le n$ and
the linear constraint</em> $$\textstyle\sum_{i=1}^n\sum_{j=1}^n M_{ij}\,w(u_i, v_j) = T\, M_{n+1,n+1}.$$</p>

<p>(<em>Proof of claim.</em> By inspection each matrix $M^{(ij)}$ in the set satisfies these constraints, so every linear combination of those matrices does.  Conversely, if $M\in\mathbb{R}^{(n+1) \times (n+1)}$ satisfies the constraints, then $M$ equals the linear combination $M'=\sum_{i=1}^n \sum_{j=1}^n \alpha_{ij} M^{(ij)}$ of the matrices, where $\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$.  Note in particular that, by the various definitions and the linear constraints,
$$\textstyle M'_{n+1,n+1} = \sum_{ij} \alpha_{ij} w(u_i, v_j)
= \sum_{ij} M_{ij} w(u_i, v_j)/T 
= (T\, M_{n+1,n+1})/T = M_{n+1,n+1}.
$$
This proves the claim.)</p>

<p>Now we show the reduction is correct.  That is, the given graph $G$ has a weight-$T$ matching if and only if the set of matrices spans a permutation matrix.</p>

<p>(<em>Only if.</em>) First suppose the given graph $G$ has a weight-$T$ perfect matching $M'$.  Let $M\in\{0,1\}^{(n+1)\times (n+1)}$ be the corresponding $n\times n$ permutation matrix, with an extra row and column added such that $M_{n+1,n+1} = 1$ and $M_{h,n+1}=M_{n+1,h}=0$ for all $h\le n$.
Then $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ is the weight of $M'$, that is, $T$, and $M_{n+1,n+1}=1$, so the linear constraints in the claim hold, and the span of the given set of matrices contains the permutation matrix $M$.</p>

<p>(<em>If.</em>) Conversely, suppose the span contains any permutation matrix $M$.  By the claim, the only non-zero entry in row $n+1$ or column $n+1$ is $M_{n+1,n+1}$, so (as $M$ is a permutation matrix) it must be that $M_{n+1,n+1} = 1$.  So deleting the last row and column gives an $n\times n$ permutation matrix. Let $M'$ be the perfect matching of $G$ corresponding to that $n\times n$ permutation matrix.  The weight of $M'$ is $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$, which (by the claim) is $T M_{n+1,n+1} = T$. So the given graph has a weight-$T$ matching, proving Lemma 2.$~~\Box$</p>

<p>Here's the delayed proof of Lemma 1:</p>

<p><em>Proof of Lemma 1.</em> Given Subset-Sum instance $(w,T)\in\mathbb{N}^n_+ \times \mathbb{N}_+$, the reduction outputs the Matching-Sum instance $(G=(U,V,E), T)$ where $U=\{u_1, u_2, \ldots, u_{2n}\}$, $V=\{v_1, v_2, \ldots, v_{2n}\}$, for each $i\in\{1,\ldots,n\}$, edge $(u_i, v_i)$ has weight $w_i$, and all remaining edges have weight zero.</p>

<p>For any perfect matching with edge weights summing to $T$, the set $S=\{i : (u_i, v_i)\in M, i\le n\}$ is a solution to the given Subset-Sum instance (as these are the only non-zero weight edges in $M$).</p>

<p>Conversely, given any solution to the Subset-Sum instance, say $S\subseteq\{1,\ldots,n\}$ with $\sum_{i\in S} w_i = T$, the set of edges $\{(u_i, v_i) : i \in S\}$ is a partial matching with weight $T$, and it extends easily to a weight-$T$ perfect matching by adding, for example, the following set of (zero-weight) edges:</p>

<p>$$\{(u_{i+n}, v_{i+n}) : i\in S\} \cup \bigcup_{i\in\{1,\ldots,n\}\setminus S}\{(u_i, v_{i+n}), (u_{i+n}, v_{i})\}.$$</p>

<p>This proves Lemma 1. The theorem follows from Lemmas 1 and 2. $~~~\Box$</p>

<hr>

<p>p.s. As an aside, according to <a href="https://cstheory.stackexchange.com/questions/41341/min-weight-perfect-matching-with-even-number-of-red-edges">this answer</a>, the restriction of Matching-Sum to instances with polynomially-bounded edge weights is in P.  But I'm sure that the restriction of the problem in the post to matrices with polynomially-bounded (integer) entries remains NP hard.</p>

CC BY-SA 4.0
2018-08-19T12:24:09.210Z
It seems like you take the convex hull of the matrices rather than the span. The span of the matrices you described is the full space of matrices. Or am I missing something?
Vanessa
CC BY-SA 4.0
2018-08-19T15:18:13.847Z
@Squark, you are correct - I misinterpreted "span". Thanks. I corrected the proof to use the correct definition of span (as any linear combination of the matrices.)
Neal Young
CC BY-SA 4.0
2018-08-25T15:33:39.170Z
Nice! I think it would be better to multiply the definition of $M^{(ij)}$ by $w(u_i,v_j)$, so that we don't have to divide by something which might be 0? Also, it seems like the proof can be somewhat simplified by combining the two reductions without the intermediate problem.
Vanessa
CC BY-SA 4.0
2018-08-25T15:39:37.953Z
Good point about dividing by zero.  I'll fix that.  I'll leave the two reductions separate though, for me it's more intuitive that way.
Neal Young
CC BY-SA 4.0
2018-08-18T17:34:42.053Z
2018-08-25T15:46:17.987Z
2018-08-25T15:46:17.987Z
Neal Young
<p>Regarding the problem of computing the diameter of a polytope presented as the intersection of halfspaces, the problem is NP-hard in general, and also NP-hard to approximate within any constant factor, see <a href="http://link.springer.com/article/10.1007/s00454-002-2756-x" rel="nofollow">Brieden's paper</a> and references therein. I think for centrally symmetric polytopes, an SDP gives an $O(\sqrt{\log m})$ approximation where $m$ is the  number of inequalities defining the polytope. I sketch this below the line.</p>

<p>In your case the Birkhoff polytope $P$ is not centrally symmetric, but working with the convex hull of $P$ and $-P$ suffices for your purposes. I <em>think</em> this "symmetric Birkhoff" polytope can be represented as the set of all square matrices $M$ that satisfy:</p>

<p>$$
\forall i^*, j^*: \sum_{i}{M_{ij^*}} =  \sum_j{M_{i^*j}} = c
$$</p>

<p>$$
\forall i,j: -1 \leq M_{ij} \leq 1
$$</p>

<p>$$
-1 \leq c \leq 1
$$</p>

<p><em>If</em> this is a correct representation (not sure), then you can just add the constraints that restrict this polytope to your given subspace. It is not hard to adapt the SDP below the line to this representation, but I choose not to go through it in order to keep notation managable.</p>

<p>I am not sure what approximate diameter does for your problem: it probably lets you decide if the given subspace is close to a permutation matrix or far from all of them, but I have not worked out the calculations. </p>

<hr>

<p>Let me finish with a sketch of the SDP rounding (which is fairly standard fare). Let $P = \{x: -b \leq Ax \leq b\}$ be a centrally symmetric polytope, where $A$ is $m \times n$. Define the vector program:</p>

<p>$\alpha^2 = \max \sum_{i = 1}^n{\|v_i\|_2^2}$</p>

<p>subject to:</p>

<p>$\forall 1 \leq i \leq m: \|\sum_{j = 1}^n{A_{ij} v_j}\|_2^2 \leq b_i^2$</p>

<p>Above the $v_i$ range over $n$-dimensional vectors. This can be written as an SDP in the standard way and is a relaxation of the diameter of $P$, i.e $\alpha$ is at least the euclidean diameter of $P$. </p>

<p>I now claim that $\alpha \leq O(\sqrt{\log m})\cdot \text{diam}(P)$. To show this,  I will give  you an algorithm that, given $(v_i)_{i=1}^n$ of value $\alpha$, outputs $x \in P$ of length at least $\frac{\alpha}{O(\sqrt{\log m})}$. The algorithm is just a random projection: pick a random $n$-dimensional vector $g$ where each $g_i$ is a standard gaussian. Set $\tilde{x}_i = g^T v_i$. By standard properties of gaussians:</p>

<p>$$
\mathbb{E}\ \|\tilde{x}\|_2^2 = \alpha^2 
$$
$$
\forall i \leq m: \mathbb{E}\ |(A\tilde{x})_i|^2 \leq b_i^2 \ \ \Rightarrow \ \ \mathbb{E}\ \max_{i=1}^m{\frac{|(A\tilde{x})_i|}{b_i}} \leq C\sqrt{\log m}.
$$
where the last bound holds for large enough $C$ (this is a standard fact about the maximum of $m$ subguassian random variables, and can be proven using the Chernoff bound). </p>

<p>The two equations already imply there exists an $x$ such that $x \in P$ and $\|x\|_2^2 \geq \frac{1}{C\sqrt{\log m}}\alpha$. Or, using concentration bounds, you can show that with constant probability $\frac{1}{2C\sqrt{\log m}}\tilde{x} \in P$ and $\|\tilde{x}\|_2\geq \frac{1}{2}\alpha$.</p>

CC BY-SA 3.0
2013-11-20T02:56:49.820Z
2013-11-20T04:21:06.907Z
2013-11-20T04:21:06.907Z
Sasho Nikolov
<p>I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix.</p>

<p>If any one knows if this problem is of a different complexity class, that would be just as helpful.</p>

<hr>

<p>EDIT: I've tagged this question with Linear Programming, because I have a strong suspicion that if such a solution existed, it would be a kind of linear programming algorithm. The reason I believe this is because the extreme points of the <a href="http://en.wikipedia.org/wiki/Birkhoff_polytope" rel="noreferrer">Birkhoff polytope</a> are precisely the permutation matrices. If you could then find an objective function which is either maximized or minimized only on the vertices of the Birkhoff polytope, you could constrain your function to the intersection of the polytope and your vector subspace, then maximize it in polynomial time. If this value were a permutation matrix, you'd know the set contained a permutation. Those are my thoughts on the subject.</p>

<hr>

<p>EDIT 2: After some more thought, it seems to me that the permutation matrices are precisely the elements of the Birkhoff Polytope with Euclidean norm $\sqrt{n}$, the we consider the Birkhoff polytope to be the convex hull of the $n \times n$ permutation matrices. Perhaps that could also be significant.</p>

<hr>

<p>EDIT 3: I added the semidefinite programming tag, because after my previous comment, I'm beginning to think that a semidefinite programming solution may be possible since it is now a linearly constrained quadratic optimization algorithm.</p>

CC BY-SA 3.0
2013-11-14T18:24:52.647Z
The entries could be in any field, there's some freedom in how to set up the matrices; however, you want a sufficiently large field (so a field of characteristic 2 would be no good for example).
Nick
CC BY-SA 3.0
2013-11-19T05:40:13.413Z
Can explain what is the span of a set of matrices?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-19T08:59:19.610Z
Mohammad : I think it is a linear combination of set of matrices.
Vivek Bagaria
CC BY-SA 3.0
2013-11-19T10:20:26.710Z
@MohammadAl-Turkistany Wikipedia: [linear span](https://en.wikipedia.org/wiki/Linear_span).
David Richerby
CC BY-SA 3.0
2013-11-19T18:43:23.693Z
@DavidRicherby I think Mohammad's confusion comes from the fact that usually we think of matrices as representing linear maps, and the span of linear map is sometimes used as another term for its range. But that doesn't make sense here, so I guess we're to think of matrices as elements of a vector space
Sasho Nikolov
CC BY-SA 3.0
2013-11-20T01:29:22.493Z
@SashoNikolov, I put back my notes from earlier. I took them down thinking I could present a clean solution and have everything looking nice for people who stumbled across the page in the future; however, you're right in that it's not a direct application of your algorithm. Just to note, the Birkhoff Polytope is defined by the linear equalities that the rows and columns sum to 1, along with the inequalities that all entries must be non-negative. I'm not sure as yet whether or not is possible to adjust for that fact.
Nick
CC BY-SA 3.0
2013-11-25T14:35:10.080Z
Is it easy to find if the span contains *some* 0/1 matrix?
Jagadish
CC BY-SA 3.0
2013-11-26T10:34:31.373Z
@Jagadish, it's true that if the Birkhoff polytope contains a binary matrix, then that matrix would necessarily be a permutation matrix. So, if you can tell whether or not the span of a set of matrices under linear inequalities contains a binary matrix, then you can indeed solve the problem. Just form the space which is the span of our matrices, plus the linear equalities and inequalities forming the Birkhoff polytope. Then test this new space for a binary matrix.
Nick
<cc.complexity-theory><linear-algebra><linear-programming><semidefinite-programming><polynomial-time>
Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?
Nick
# Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

(Asked by: username_0 on 2013-11-14)

I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix.

If any one knows if this problem is of a different complexity class, that would be just as helpful.

---

EDIT: I've tagged this question with Linear Programming, because I have a strong suspicion that if such a solution existed, it would be a kind of linear programming algorithm. The reason I believe this is because the extreme points of the [Birkhoff polytope](http://en.wikipedia.org/wiki/Birkhoff_polytope) are precisely the permutation matrices. If you could then find an objective function which is either maximized or minimized only on the vertices of the Birkhoff polytope, you could constrain your function to the intersection of the polytope and your vector subspace, then maximize it in polynomial time. If this value were a permutation matrix, you'd know the set contained a permutation. Those are my thoughts on the subject.

---

EDIT 2: After some more thought, it seems to me that the permutation matrices are precisely the elements of the Birkhoff Polytope with Euclidean norm $\sqrt{n}$, the we consider the Birkhoff polytope to be the convex hull of the $n \times n$ permutation matrices. Perhaps that could also be significant.

---

EDIT 3: I added the semidefinite programming tag, because after my previous comment, I'm beginning to think that a semidefinite programming solution may be possible since it is now a linearly constrained quadratic optimization algorithm.

**Tags:** cc.complexity-theory, linear-algebra, linear-programming, semidefinite-programming, polynomial-time
> **Comments:**
> **username_0**: The entries could be in any field, there's some freedom in how to set up the matrices; however, you want a sufficiently large field (so a field of characteristic 2 would be no good for example).  
> **username_1**: Can explain what is the span of a set of matrices?  
> **username_2**: Mohammad : I think it is a linear combination of set of matrices.  
> **username_3**: @MohammadAl-Turkistany Wikipedia: [linear span](https://en.wikipedia.org/wiki/Linear_span).  
> **username_4**: @DavidRicherby I think Mohammad's confusion comes from the fact that usually we think of matrices as representing linear maps, and the span of linear map is sometimes used as another term for its range. But that doesn't make sense here, so I guess we're to think of matrices as elements of a vector space  
> **username_0**: @SashoNikolov, I put back my notes from earlier. I took them down thinking I could present a clean solution and have everything looking nice for people who stumbled across the page in the future; however, you're right in that it's not a direct application of your algorithm. Just to note, the Birkhoff Polytope is defined by the linear equalities that the rows and columns sum to 1, along with the inequalities that all entries must be non-negative. I'm not sure as yet whether or not is possible to adjust for that fact.  
> **username_5**: Is it easy to find if the span contains *some* 0/1 matrix?  
> **username_0**: @Jagadish, it's true that if the Birkhoff polytope contains a binary matrix, then that matrix would necessarily be a permutation matrix. So, if you can tell whether or not the span of a set of matrices under linear inequalities contains a binary matrix, then you can indeed solve the problem. Just form the space which is the span of our matrices, plus the linear equalities and inequalities forming the Birkhoff polytope. Then test this new space for a binary matrix.  

---

## 2 answers

### Answer by username_6 on 2018-08-18. Score: 5

> **Theorem.** *The problem in the post is NP-hard, by reduction from Subset-Sum.*

Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op.

---

Here is the intuition. The problem in the post is

* *Is there a permutation matrix in the span of a given set of matrices?*

This is essentially the same as

* *Is there a permutation matrix that (thinking of the matrix as a vector) satisfies some given linear constraints?*

This in turn is the same as

* *Is there a perfect matching (in a complete bipartite graph) whose incidence vector satisfies some given linear constraints?*

Reducing Subset-Sum to the latter problem is a standard exercise.

Here is the detailed proof.

---

Define the following intermediate problem:

> **Matching-Sum:**
>
> **input:** *Complete, bipartite graph $G=(U,V,E)$ with non-negative
> integer edge weights, and non-negative integer target $T$.*
>
> **output:** *Does $G$ contain a perfect matching of weight exactly $T$?*

---

> **Lemma 1**. *Subset-Sum poly-time reduces to Matching-Sum.*

Proving this is a standard homework exercise. The proof is at the end.

> **Lemma 2.** *Matching-Sum poly-time reduces to the problem in the post.*

*Proof of Lemma 2.* Fix a Matching-Sum input: a complete bipartite graph $G=(U,V,E)$ with non-negative integer edge weights $w:U\times V\rightarrow \mathbb{N}\_+$, and target $T\in \mathbb{N}\_+$, where $U=\{u\_1,\ldots,u\_n\}$ and $V=\{v\_1, \ldots, v\_n\}$. For each $i,j\in\{1,2,\ldots,n\}$, define $M^{(ij)}$ to be the matrix in $\mathbb{R}^{(n+1)\times (n+1)}$ where $M^{(ij)}\_{ij} = T$, and $M^{(ij)}\_{n+1,n+1}=w(u\_i, v\_j)$, and all other entries are zero. The reduction outputs the following set of matrices:
$$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$$
This defines the reduction.

**Claim.** *The span of this set of matrices consists of
those matrices $M \in\mathbb{R}^{(n+1)\times(n+1)}$ satisfying
the linear constraints $M\_{h,n+1} = M\_{n+1,h} = 0$ for all $h\le n$ and
the linear constraint* $$\textstyle\sum\_{i=1}^n\sum\_{j=1}^n M\_{ij}\,w(u\_i, v\_j) = T\, M\_{n+1,n+1}.$$

(*Proof of claim.* By inspection each matrix $M^{(ij)}$ in the set satisfies these constraints, so every linear combination of those matrices does. Conversely, if $M\in\mathbb{R}^{(n+1) \times (n+1)}$ satisfies the constraints, then $M$ equals the linear combination $M'=\sum\_{i=1}^n \sum\_{j=1}^n \alpha\_{ij} M^{(ij)}$ of the matrices, where $\alpha\_{ij} = M\_{ij}/M^{(ij)}\_{ij} = M\_{ij}/T$. Note in particular that, by the various definitions and the linear constraints,
$$\textstyle M'\_{n+1,n+1} = \sum\_{ij} \alpha\_{ij} w(u\_i, v\_j)
= \sum\_{ij} M\_{ij} w(u\_i, v\_j)/T
= (T\, M\_{n+1,n+1})/T = M\_{n+1,n+1}.
$$
This proves the claim.)

Now we show the reduction is correct. That is, the given graph $G$ has a weight-$T$ matching if and only if the set of matrices spans a permutation matrix.

(*Only if.*) First suppose the given graph $G$ has a weight-$T$ perfect matching $M'$. Let $M\in\{0,1\}^{(n+1)\times (n+1)}$ be the corresponding $n\times n$ permutation matrix, with an extra row and column added such that $M\_{n+1,n+1} = 1$ and $M\_{h,n+1}=M\_{n+1,h}=0$ for all $h\le n$.
Then $\sum\_{i=1}^n\sum\_{j=1}^n M\_{ij} w(u\_i, v\_j)$ is the weight of $M'$, that is, $T$, and $M\_{n+1,n+1}=1$, so the linear constraints in the claim hold, and the span of the given set of matrices contains the permutation matrix $M$.

(*If.*) Conversely, suppose the span contains any permutation matrix $M$. By the claim, the only non-zero entry in row $n+1$ or column $n+1$ is $M\_{n+1,n+1}$, so (as $M$ is a permutation matrix) it must be that $M\_{n+1,n+1} = 1$. So deleting the last row and column gives an $n\times n$ permutation matrix. Let $M'$ be the perfect matching of $G$ corresponding to that $n\times n$ permutation matrix. The weight of $M'$ is $\sum\_{i=1}^n\sum\_{j=1}^n M\_{ij} w(u\_i, v\_j)$, which (by the claim) is $T M\_{n+1,n+1} = T$. So the given graph has a weight-$T$ matching, proving Lemma 2.$~~\Box$

Here's the delayed proof of Lemma 1:

*Proof of Lemma 1.* Given Subset-Sum instance $(w,T)\in\mathbb{N}^n\_+ \times \mathbb{N}\_+$, the reduction outputs the Matching-Sum instance $(G=(U,V,E), T)$ where $U=\{u\_1, u\_2, \ldots, u\_{2n}\}$, $V=\{v\_1, v\_2, \ldots, v\_{2n}\}$, for each $i\in\{1,\ldots,n\}$, edge $(u\_i, v\_i)$ has weight $w\_i$, and all remaining edges have weight zero.

For any perfect matching with edge weights summing to $T$, the set $S=\{i : (u\_i, v\_i)\in M, i\le n\}$ is a solution to the given Subset-Sum instance (as these are the only non-zero weight edges in $M$).

Conversely, given any solution to the Subset-Sum instance, say $S\subseteq\{1,\ldots,n\}$ with $\sum\_{i\in S} w\_i = T$, the set of edges $\{(u\_i, v\_i) : i \in S\}$ is a partial matching with weight $T$, and it extends easily to a weight-$T$ perfect matching by adding, for example, the following set of (zero-weight) edges:

$$\{(u\_{i+n}, v\_{i+n}) : i\in S\} \cup \bigcup\_{i\in\{1,\ldots,n\}\setminus S}\{(u\_i, v\_{i+n}), (u\_{i+n}, v\_{i})\}.$$

This proves Lemma 1. The theorem follows from Lemmas 1 and 2. $~~~\Box$

---

p.s. As an aside, according to [this answer](https://cstheory.stackexchange.com/questions/41341/min-weight-perfect-matching-with-even-number-of-red-edges), the restriction of Matching-Sum to instances with polynomially-bounded edge weights is in P. But I'm sure that the restriction of the problem in the post to matrices with polynomially-bounded (integer) entries remains NP hard.

> **Comments:**
> **username_7**: It seems like you take the convex hull of the matrices rather than the span. The span of the matrices you described is the full space of matrices. Or am I missing something?  
> **username_6**: @Squark, you are correct - I misinterpreted "span". Thanks. I corrected the proof to use the correct definition of span (as any linear combination of the matrices.)  
> **username_7**: Nice! I think it would be better to multiply the definition of $M^{(ij)}$ by $w(u_i,v_j)$, so that we don't have to divide by something which might be 0? Also, it seems like the proof can be somewhat simplified by combining the two reductions without the intermediate problem.  
> **username_6**: Good point about dividing by zero.  I'll fix that.  I'll leave the two reductions separate though, for me it's more intuitive that way.  

---

### Answer by username_4 on 2013-11-20. Score: 3

Regarding the problem of computing the diameter of a polytope presented as the intersection of halfspaces, the problem is NP-hard in general, and also NP-hard to approximate within any constant factor, see [Brieden's paper](http://link.springer.com/article/10.1007/s00454-002-2756-x) and references therein. I think for centrally symmetric polytopes, an SDP gives an $O(\sqrt{\log m})$ approximation where $m$ is the number of inequalities defining the polytope. I sketch this below the line.

In your case the Birkhoff polytope $P$ is not centrally symmetric, but working with the convex hull of $P$ and $-P$ suffices for your purposes. I *think* this "symmetric Birkhoff" polytope can be represented as the set of all square matrices $M$ that satisfy:

$$
\forall i^\*, j^\*: \sum\_{i}{M\_{ij^\*}} = \sum\_j{M\_{i^\*j}} = c
$$

$$
\forall i,j: -1 \leq M\_{ij} \leq 1
$$

$$
-1 \leq c \leq 1
$$

*If* this is a correct representation (not sure), then you can just add the constraints that restrict this polytope to your given subspace. It is not hard to adapt the SDP below the line to this representation, but I choose not to go through it in order to keep notation managable.

I am not sure what approximate diameter does for your problem: it probably lets you decide if the given subspace is close to a permutation matrix or far from all of them, but I have not worked out the calculations.

---

Let me finish with a sketch of the SDP rounding (which is fairly standard fare). Let $P = \{x: -b \leq Ax \leq b\}$ be a centrally symmetric polytope, where $A$ is $m \times n$. Define the vector program:

$\alpha^2 = \max \sum\_{i = 1}^n{\|v\_i\|\_2^2}$

subject to:

$\forall 1 \leq i \leq m: \|\sum\_{j = 1}^n{A\_{ij} v\_j}\|\_2^2 \leq b\_i^2$

Above the $v\_i$ range over $n$-dimensional vectors. This can be written as an SDP in the standard way and is a relaxation of the diameter of $P$, i.e $\alpha$ is at least the euclidean diameter of $P$.

I now claim that $\alpha \leq O(\sqrt{\log m})\cdot \text{diam}(P)$. To show this, I will give you an algorithm that, given $(v\_i)\_{i=1}^n$ of value $\alpha$, outputs $x \in P$ of length at least $\frac{\alpha}{O(\sqrt{\log m})}$. The algorithm is just a random projection: pick a random $n$-dimensional vector $g$ where each $g\_i$ is a standard gaussian. Set $\tilde{x}\_i = g^T v\_i$. By standard properties of gaussians:

$$
\mathbb{E}\ \|\tilde{x}\|\_2^2 = \alpha^2
$$
$$
\forall i \leq m: \mathbb{E}\ |(A\tilde{x})\_i|^2 \leq b\_i^2 \ \ \Rightarrow \ \ \mathbb{E}\ \max\_{i=1}^m{\frac{|(A\tilde{x})\_i|}{b\_i}} \leq C\sqrt{\log m}.
$$
where the last bound holds for large enough $C$ (this is a standard fact about the maximum of $m$ subguassian random variables, and can be proven using the Chernoff bound).

The two equations already imply there exists an $x$ such that $x \in P$ and $\|x\|\_2^2 \geq \frac{1}{C\sqrt{\log m}}\alpha$. Or, using concentration bounds, you can show that with constant probability $\frac{1}{2C\sqrt{\log m}}\tilde{x} \in P$ and $\|\tilde{x}\|\_2\geq \frac{1}{2}\alpha$.


---

