Probability measures on the symmetric group vs. the probabilities $P(\sigma(k) = l)$ Suppose we are given a random variable $\sigma : \Omega \to S_n$ on the symmetric group of $n$ letters and we are given numbers representing the probabilities
$$p_{k,l} = \mathbb P(\sigma(k) = l).$$
Ignore for now that they are defined via the distribution of $\sigma$ and just consider numbers $p_{k,l} \geq 0$ with $\sum_{k=1}^n p_{k,l} = \sum_{l=1}^n p_{k,l} = 1$.
Does there always exist a distribution, i.e. probabilities $\mathbb P(\sigma = \tau)$ summing to $1$, such that $p_{k,l} = \mathbb P(\sigma(k) = l)$? Is there a canonical choice (maybe with maximal support)?

Of course, we have
$$\mathbb P(\sigma = \tau) = \mathbb P(\sigma(1) = \tau(1),\dots, \sigma(n) = \tau(n)),$$
but the joint distribution of $(\sigma (1),\dots, \sigma(n))$ is not known and they cannot be considered as independent.
We can write
$$\mathbb P(\sigma = \tau) = \mathbb P(\sigma(1) = \tau(1)|\sigma = \tau\text{ on } \{2,\dots, N\}) \mathbb P(\sigma(2) = \tau(3)|\sigma = \tau\text{ on } \{3,\dots, N\})\cdots \mathbb P(\sigma_N = \tau_N),$$
and this seems to be in the "permutation spirit", but I still don't see what probabilities one should use here.

Note that we are given $N^2$ numbers, but need to determine $N!$ numbers. The distribution of $\sigma$ cannot be unique in general as the following example shows:
Let $G$ be a transitive subgroup of $S_n$ and suppose $\sigma$ has uniform distribution on $G$. Then
$$\mathbb P(\sigma(k) = l) = \sum_{\tau \in G} \mathbb P(\sigma(k) = l|\sigma = \tau) \mathbb P(\sigma = \tau) = \frac{1}{|G|} |\{\tau \in G : \tau(l) = j\}|.$$
By the transitivity there exists a $\pi\in G$, such that $\pi(j) = l$. So
$$|\{\tau \in G : \tau(l) = j\}| = |\{\tau \in G : \pi\circ \tau(l) = \pi(l)\}| = |\{\tau \in G : \tau(l) = l\}| = |\operatorname{Stb}(l)|,$$
where $\operatorname{Stb}(l)$ is the stabilizer of $l$ under the action of $G$ on $\{1,\dots, n\}$. Since the action is transitive and by the orbit-stabilizer theorem we have
$$|\operatorname{Stb}(l)| = \frac{|G|}{N}.$$
Therefore,
$$\mathbb P(\sigma(k) = l) = \frac1N.$$
Notably, this does not depend on $G$. By choosing $G = S_n$ and $G = A_n$ (alternating group) we get two different distributions for $\sigma$ with the same probabilities $\mathbb P(\sigma(k) = l)$.
 A: Yes, a distribution always exists. The matrix $P:=(p_{k,\ell})_{k,\ell=1}^n$ is doubly stochastic, so the Birkhoff–von Neumann theorem implies that $P$is a convex combination of permutation matrices. That is, $P=\sum_{i=1}^m a_i Q_i$, where $a_i\ge 0$, $\sum_{i=1}^m a_i=1$, and each $Q_i$ is a permutation matrix. This defines a distribution on $S_n$, where $P(\pi_i)=a_i$ for the permutation $\pi_i$ associated to $Q_i$.
I cannot say anything about a canonical choice of distribution.
A: You have an $n\times n$ matrix $P$ of non-negative real numbers, where each row and column sums to $1$.
Partition the columns into sets $C_1\sqcup C_2$, and partition the rows into sets $R_1\sqcup R_2$. Let $$\Delta_{st}=\sum_{i\in R_s}\sum_{j\in C_t} P_{ij},$$
for $s,t\in\{1,2\}$.
Then $$\Delta_{1t}+\Delta_{2t}=|C_t|,\qquad\qquad \Delta_{s1}+\Delta_{s2}=|R_s|,$$
using the fact that the rows and columns of $P$ sum to $1$.
In particular, suppose that $P_{ij}=0$ whenever both $i\in R_2, j\in C_2.$
Then $\Delta_{22}=0$, so we have $$\Delta_{21}=|R_2|,\qquad\qquad \Delta_{11}+\Delta_{21}=|C_1|.$$
As $\Delta_{11}$ is a sum of non-negative real numbers, we know $\Delta_{11}\geq0$.  We conclude:$$\qquad\qquad\qquad|C_1|\geq |R_2|\qquad\qquad \qquad (1).$$
Then for any set of rows $R$, we can let $R_2=R$, and let $C_2$ be the set of columns which intersect all the rows of $R$ in entries equal to $0$.  Letting $R_1,C_1$ be the complements of $R_2,C_2$ respectively, the result $(1)$ tells us that the number of columns which have a positive entry on some row of $R$ is at least $|R|$.
To see the importance of this result, construct the bipartite graph $G_P$ with nodes the rows and columns of $P$, where we place an edge between a row and column precisely when the entry of $P$ in their intersection is positive.
Then $(1)$ is precisely the statement that $G_P$ satisfies Hall's marriage condition: For any set of rows $R$, the number of columns adjacent to  some element of $R$, is at least $|R|$.
By Hall's marriage theorem we may conclude that we have a bijection from rows to columns, such that the entry in the intersection of any row and its corresponding column, is positive.
In other words, we have a permutation matrix $Q$, such that $$\qquad\qquad \qquad Q_{ij}=1\implies P_{ij}>0.\qquad\qquad \qquad(2)$$
Now let $$a=\min \{P_{ij}|\,\,Q_{ij}=1\}.$$
Then $(2)$ implies that $a>0$.  Clearly $a\leq 1$.  If $a<1$ let $$P'=\frac1{1-a}P-\frac a{1-a}Q.$$
Then the rows and columns of $P'$ all add up to $1$.  The entries of $P'$ are all non-negative, and if $P_{ij}=a$ and $Q_{ij}=1$ then $P'_{ij}=0$.  That is $P'$ has strictly more $0$'s than $P$.  Also:$$
(1-a)P'+aQ =P.$$
That is $P$ is a convex linear combination of a permutation matrix $Q$, and a matrix $P'$ satisfying the same hypothesis' as $P$, but with strictly more $0$'s.
Repeatedly applying this process, the number of non-zero entries in our matrix goes down, so the process cannot repeat indefinitely.  That is eventually $a=1$, and our matrix is a permutation matrix.
That is, we have a sequence of matrices $$P=P_0,P_1,\cdots, P_m=Q_{m+1},$$
and $$Q_1,Q_2,\cdots, Q_m,$$ where the $Q_i$ are permutation matrices and $P_i$ is a convex linear combination of $P_{i+1}$ and $Q_{i+1}$, for $i<m$.
Then $$P=\sum_{i=1}^{m+1} p_i Q_i,$$ where the $p_i$ are non-negative real numbers summing to $1$.
Finally we assign the permutation represented by each $Q_i$ the probability $p_i$ of being selected (and all other permutations are assigned probability $0$ of being selected).  If $\sigma$ is selected by these means, then $$\mathbb{P}(\sigma_i=j)=P_{ij},$$ as required.
