# 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

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?

• I don't quite understand this question—for example, is it a question about a particular matrix $A$, or about any matrix?—but this seems to be an elementary probability question, not a research-level question, and so does not belong on MO. If you want to clarify it for MO, or ask it again on MSE, I encourage you to TeX it so that it will be easier to read. – LSpice May 10 at 0:43
• Welcome to MO. It's good to have an example, but eventually the question is really unclear. It might be that the question would eventually fit MO, but I currently can't quite follow. Use crisper definitions and state a more precise question. – Amir Sagiv May 10 at 0:46
• Thank you @LSpice for your comments and suggestions. I rephrased the problem, detailed it better, and used LaTex. I don't know if it fits better here or on MSE. – Carlos A. Astudillo Trujillo May 10 at 2:10
• Thank you @AmirSagiv. I tried to explain better the problem. Please help me to define if it fits better here or on MSE. – Carlos A. Astudillo Trujillo May 10 at 2:11
• It seems to me that it would be clearer to phrase this without the matrix. – user44191 May 10 at 14:57

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.$$
• Thank you @Max for your answer. It seems that in your solution $m$ is the number of unique selected elements, is it right? – Carlos A. Astudillo Trujillo May 10 at 13:27
• Another option to answer my initial question is just to consider $m$ as $m^{′}$ in your formula without replacement and calculate $m{′}=N{\cdot}k\left(1−B_{0}(n,p)\right)$, where $B_{r}(n,p)$ is the binomial distribution with parameters $n=m$ (as defined in the initial question), $p=\frac{1}{N{\cdot}k}$ and $r$ is the number of times an element in $S_k$ is selected. Thus, $1−B_{0}(n,p)$ is the probability that an element of $S_{k}$ is selected at least once in $n$ trials. – Carlos A. Astudillo Trujillo May 10 at 14:30
• I tested your solution of selection with replacement and it is more accurate than my previous suggestion of considering $m^{'}$ and selection without replacement. Thank you again. – Carlos A. Astudillo Trujillo May 10 at 15:22