Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?
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, 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.