Let $A\_{N{\times}N}$ be an $N{\times}N$ matrix and $\mathcal{S\_{k}}$ be a subset of elements in $A$ such that exactly $k$ elements from every row and column in $A$ are in $\mathcal{S\_{k}}$. Thus, $\mathcal{S\_k}$ has cardinality $N{\cdot}k$, with $k \in \{1,2,..,N\}$.


\begin{equation\*}
A\_{N,N} = 
\begin{pmatrix}
a\_{1,1} & a\_{1,2} & \cdots & a\_{1,N} \\
a\_{2,1} & a\_{2,2} & \cdots & a\_{2,N} \\
\vdots & \vdots & \ddots & \vdots \\
a\_{N,1} & a\_{N,2} & \cdots & a\_{N,N} 
\end{pmatrix}
\end{equation\*}


For instance, consider $A\_{8{\times}8}$ as described below. 
Let subset $S\_{2}$ of the matrix $A\_{8{\times}8}$ be given by the elements in bold in $A\_{8{\times}8}$. Note that $S$ can be any subset having as its elements exactly $k=2$ elements per column and row of $A\_{8{\times}8}$. 


\begin{equation\*}
A\_{8,8} = 
\begin{pmatrix}
\mathbf{a\_{1,1}} & a\_{1,2} & a\_{1,3} & a\_{1,4} & a\_{1,5} & a\_{1,6} & a\_{1,7} & \mathbf{a\_{1,8}} \\
\mathbf{a\_{2,1}} & \mathbf{a\_{2,2}} & a\_{2,3} & a\_{2,4} & a\_{2,5} & a\_{2,6} & a\_{2,7} & a\_{2,8} \\
a\_{3,1} & \mathbf{a\_{3,2}} & \mathbf{a\_{3,3}} & a\_{3,4} & a\_{3,5} & a\_{3,6} & a\_{3,7} & a\_{3,8} \\
a\_{4,1} & a\_{4,2} & \mathbf{a\_{4,3}} & \mathbf{a\_{4,4}} & a\_{4,5} & a\_{4,6} & a\_{4,7} & a\_{4,8} \\
a\_{5,1} & a\_{5,2} & a\_{5,3} & \mathbf{a\_{5,4}} & \mathbf{a\_{5,5}} & a\_{5,6} & a\_{5,7} & a\_{5,8} \\
a\_{6,1} & a\_{6,2} & a\_{6,3} & a\_{6,4} & \mathbf{a\_{6,5}} & \mathbf{a\_{6,6}} & a\_{6,7} & a\_{6,8} \\
a\_{7,1} & a\_{7,2} & a\_{7,3} & a\_{7,4} & a\_{7,5} & \mathbf{a\_{7,6}} & \mathbf{a\_{7,7}} & a\_{7,8} \\
a\_{8,1} & a\_{8,2} & a\_{8,3} & a\_{8,4} & a\_{8,5} & a\_{8,6} & \mathbf{a\_{8,7}} & \mathbf{a\_{8,8}}
\end{pmatrix}
\end{equation\*}


Now, select randomly $m$ elements from $\mathcal{S\_{k}}$ with replacement. Then, we create an induced matrix with just the rows and columns of $A\_{N{\times}N}$ corresponding to the selected elements from $\mathcal{S\_{k}}$.
For instance, if after selecting $m$ elements with replacement, the uniquely selected elements from $S\_{2}$ are the following 5 elements: $a\_{1,1},a\_{3,2},a\_{3,3},a\_{6,6},a\_{8,8}$, then the resultant matrix is


\begin{equation\*}
A\_{r} = 
\begin{pmatrix}
\mathbf{a\_{1,1}} & a\_{1,2} & a\_{1,3} & a\_{1,6} & \mathbf{a\_{1,8}} \\
a\_{3,1} & \mathbf{a\_{3,2}} & \mathbf{a\_{3,3}} & a\_{3,6} & a\_{3,8} \\
a\_{6,1} & a\_{6,2} & a\_{6,3} & \mathbf{a\_{6,6}} & a\_{6,8} \\
a\_{8,1} & a\_{8,2} & a\_{8,3} & a\_{8,6} & \mathbf{a\_{8,8}}
\end{pmatrix}
\end{equation\*}


Let $X$ be the number of elements in $\mathcal{S\_{k}}$ of the resultant matrix ($A\_{r}$). For the given example, $x=6$.


My Question: How we can calculate the average of $X$ for given $m,N,k$ ($E[X](N,k,m))$?


I have already calculated the average number of columns $E(C)$ when $m$ elements are randomly selected with replacement from $\mathcal{S\_{k}}$. Note that for this case $E(C)$ is equal to the average number of rows $E(R)$ and can be calculated as:


$E[C](N,m)=N\*P\_{chosen}$, where $P\_{chosen}=1-(1-(1/N))^m)$ is the probability that a column of the original matrix is selected at least once. Thus, $A\_{r}$ is a $E[C] \times E[R]$ matrix.


Thank you for any help! 




---


An alternative phrasing:
Write $I\_N = \{1, 2, \cdots, N\}$. Let $S \in I\_N \times I\_N$ be a subset such that $|S \cap (\{i\} \times I\_N)| = |S \cap (I\_N \times \{i\})| = 2$. Note that $|S| = 2N$.


Then for given $0 \leq m \leq 2k$, what is the distribution of $|p\_1(M)| |p\_2(M\_m)|$, where $M\_m$ ranges uniformly over the set of $m$-element subsets of $S$, and $p\_1, p\_2$ are the projection functions?



Average number of elements of a subset S of a matrix A after inducing the rows and columns of m randomly selected elements from subset S
Suppose that we selected $m$ random elements of $S\_k$. An element $s$ of $S\_k$ appears in the induced matrix iff (i) there is a selected element in the row of $s$ in $A$; and (ii) there is a selected element in the column of $s$ in $A$. Call such an element $s$ *lucky*, and so $X$ is the number of lucky elements.


Under selection without replacement, the probability $P$ of a fixed element $s\in S\_k$ to be lucky equals 
$$P = 1 - \frac{2\binom{Nk-k}{m} - \binom{Nk-(2k-1)}{m}}{\binom{Nk}{m}},$$
where $\binom{Nk-k}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from the row of $s$ in $A$, and $\binom{Nk-(2k-1)}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from neither the row nor the column of $s$ in $A$.


Similarly, under selection with replacement, we have 
$$P = 1 - \frac{2(Nk-k)^m - (Nk-(2k-1))^m}{(Nk)^m}.$$


Then
$$E[X](m,N,k) = Nk\cdot P.$$


