After extensive comments by @loupblanc, and reviewing by myself, I've decided to rewrite the question, and change the matrices.
Let $p_k$ be the $k$th prime number, so that $p_1=2, p_2=3, \dots$
We will create a Toepliz matrix from some circulant matrices. Define $R_p$ to be be a $p \times p$ circulant matrix, whose top row is filled with random numbers, and thus the rest of the circulant matrix has elements according to the definition of a circulant matrix. Also,define:
$$A_{n,k}=M_{n,2}+M_{n,3}+\cdots+M_{n,p_k}$$
...where $M_{n,p}[i,j]=R_p[i_1,j_1]$, with $i_1=i \bmod p$ if $i \bmod p \ne 0$ and $i_1=p$ otherwise, and similarly for $j_1$. We note that $A_{n,k}$ is therefor a Toeplitz matrix.
Given $k$, we can search for the maximum $n$ such that $A_{n,k}$ is invertible. Let $f(k)$ be this maximum rank, i.e. $f(k)=n$. It is then conjectured that $f(k)=2+3+5+\cdots+p_k-(k-1)$. Is this conjecture true?
OLD QUESTION
A few definitions should help... Let $R_p$ be a $p \times p$ matrix of random numbers. Now let $M_p$ be the $n \times n$ matrix "tiled" by $R_p$. In other words, $M_p(i,j) = R_p(i \bmod p, j \bmod p)$, or $M_p$ consists of block matrices which are equal to $R_p$:
$$M_p = \begin{bmatrix} R_p & R_p & R_p & \dots \\ R_p & R_p & R_p & \dots \\ R_p & R_p & R_p & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$
Thus, as we proceed across $M_p$, or down $M_p$, the coefficients must repeat every $p$ coefficients.
Suppose we create a matrix $A = M_2 + M_3 + M_5 + M_7 + \dots + M_\text{prime numbers} + \dots$. In other words, we create matrices by adding together the tilings of prime number-sized block matrices.
If $A$ is then an $n \times n$ matrix, how many $M_p$'s do we need, starting with $M_2$, to create a nonsingular $A$? To rephrase, if we start with $M_2$, add $M_3$, add $M_5$, and so on, how many do we need to add together to get a non-singular matrix (which is of course of size $n \times n$)?
I conjecture that we need roughly $n^{1/2}$ of them, but I need help proving this. I believe this is because each $M_p$ adds approximately $p$ to the current rank of $A$. I'm stuck, though, and could use some help.
EDIT
The main problem in this question seems to be what the rank of $A$ is, given the $M_p$ matrices that are used. It seems that some of the rows and/or columns of the matrices are redundant, so the problem is basically to find out how large the rank is.
I rarely read a so unclear post. Let $p_k$ be the $k^{th}$ prime number (of the list $2,3,5,\cdots$). You must absolutely explicitly define the matrix $A_{n,k}\in M_n$, for example, as follows:
$A_{n,k}=M_{n,2}+M_{n,3}+\cdots+M_{n,p_k}$ where $M_{n,p}[i,j]=R_p[i_1,j_1]$, with $i_1=i\; mod\; p$ if $i\; mod\; p<>0$ and $i_1=p$ otherwise (similar definition for $j_1$). In particular $M_{n,p}$ is not tiled by the $R_p$ because you use scissors!
For a fixed $n$, you search the minimum of $k$ s.t. $A_{n,k}$ is invertible. In general, such a problem is difficult; yet, in $M_{n,p_k}$ (the last matrix), there are still many copies of the matrix $R_{p_k}$ and I think that the problem is feasible.
i) I think that it is better to consider that $k$ is given and to research the maximum of the $n$ s.t. $A_{n,k}$ is invertible. Indeed, when the $R_p$ are randomly chosen, $A_{n,k}$ is "always" invertible or "always" non-invertible. Moreover, if $A_{n,k}$ is invertible, then the $A_{m,k}$, with $m<n$, are "always" invertible.
ii) Then let $f(k)$ be this maximal $n$. Several calculations seem to "prove":
Conjecture (it may be the meaning of the last Matt Groff's comment): $f(k)=2+3\cdots+p_k-k+1$.
I think that it is much better to rewrite your post, using the lines above (definition of $A_{n,k}$ and conjecture).