Skip to main content
4 of 7
adding number of m elements in the example; added 2 characters in body

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. The subset $S_{2}$ of the matrix $A_{8{\times}8}$ is given by the elements in bold in $A_{8{\times}8}$. Note that $S$ has as 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!