Do There Exist Two Random Vectors Having a Given Matrix as their Cross-Covariance Matrix? 
Does there exist two random vectors $\mathbf{X}$ and $\mathbf{Y}$ having the following matrix as their covariance matrix? i.e each entry $(i,j)$ of the matrix is $Cov(X_i,Y_j)$ If not, explain why. If yes, give an example.
$$\Sigma_1 = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \Sigma_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \Sigma_3 = \begin{bmatrix}1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \Sigma_4 =  \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0  \end{bmatrix}, \Sigma_5 = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{bmatrix}, \Sigma_6 = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1\end{bmatrix}$$

I don't know if there are any general properties of cross-covariance matrices like there are for  regular covariance matrices? Obviously if $Cov(X,Y)$ is an $mxn$ matrix then $X$ is $mx1$ and $Y$ is $nx1$. But other than that I believe any matrix could be a cross-covariance matrix?
Not sure what examples to give of vectors other than to say the dimensions of the vectors must match the matrix (like I explained previously), and the vectors must have the property that $Cov(X_i,Y_j)$ corresponds to each entry $i,j$ in the matrix. Also, in the case of $\Sigma_1$ the vectors must be uncorrelated.
 A: You are correct: any matrix can be a cross-covariance matrix.  But it doesn't look straightforward to prove.  Here is an outline of a proof and an effective algorithm for finding the random variables $X$ and $Y$.

Let $B$ be an $m\times n$ real matrix (which could be any of the $\Sigma_i$ in the question).  Replacing $B$ with its transpose $B^\prime$ if necessary, we may assume without any loss of generality that $m \le n.$
First, find an $m\times m$ invertible matrix $S$ and an $n\times n$ invertible matrix $T$ for which $S\,B\,T$ is diagonal.  This is the Smith normal form of $B.$ It can be found by row-reducing and then column-reducing $B.$  Because the coefficients of $B$ are in a field, we may take the first $r$ diagonal elements of $SBT$ to be unity and the remaining ones to be zero, where of course $0\le r \le m.$  In block-matrix notation this means
$$S\,B\,T = \left(\begin{array}{c|c} \mathbb{I}_r & \mathbb{O}_{r\times n-r}\\ \hline \mathbb{O}_{m-r\times r} & \mathbb{O}_{m-r\times n-r}\end{array}\right)$$
The $\mathbb{I}$ matrix is the $r\times r$ identity and all the $\mathbb{O}$ matrices are zero-matrices; subscripts denote the dimensions.
This (by inspection) could be the off-diagonal block of an $m+n\times m+n$ covariance matrix provided there are $r$ pairs of perfectly correlated variables.  In light of this, consider the $m\times m$ matrix $A$ with
$$A = \left(\begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times m-r}\\ \hline \mathbb{O}_{m-r\times r} & \mathbb{I}_{m-r\times m-r}\end{array}\right)$$
and the $n\times n$ matrix $\Delta$ with
$$\Delta = \left(\begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times n-r}\\ \hline \mathbb{O}_{n-r\times r} & \mathbb{I}_{n-r\times n-r}\end{array}\right)$$
Here, $\mathbf{1}_r$ is the column $r$-vector of ones.
From these three ingredients form the $m+n\times m+n$ matrix
$$\Upsilon = \left(\begin{array}{c|c} A & S\,B\,T\\ \hline T^\prime B^\prime S^\prime & \Delta\end{array}\right) 
= \left(\begin{array}{c|c} \begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times m-r}\\ 
\hline \mathbb{O}_{m-r\times r} & \mathbb{I}_{m-r\times m-r}\end{array} & \begin{array}{c|c} \mathbb{I}_r & \mathbb{O}_{r\times n-r}\\ 
\hline \mathbb{O}_{m-r\times r} & \mathbb{O}_{m-r\times n-r}\end{array}\\ 
\hline \begin{array}{c|c} \mathbb{I}_r & \mathbb{O}_{r\times m-r}\\ 
\hline \mathbb{O}_{n-r\times r} & \mathbb{O}_{n-r\times m-r}\end{array} & \begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times n-r}\\ 
\hline \mathbb{O}_{n-r\times r} & \mathbb{I}_{n-r\times n-r}\end{array}\end{array}\right)$$
This matrix $\Upsilon$ is positive semi-definite (and therefore is a covariance matrix).  To see this, permute the rows and columns to put the two blocks of ones in the upper left, producing the equivalent matrix
$$\Upsilon_0 = \left(\begin{array}{c|c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times r}& \mathbb{O}_{r\times m+n-2r}\\ 
\hline \mathbb{O}_{r\times r} & \mathbf{1}_r\,\mathbf{1}_r^\prime  & \mathbb{O}_{r\times m+n-2r}\\
\hline \mathbb{O}_{m+n-2r \times r} & \mathbb{O}_{m+n-2r\times r} & \mathbb{I}_{m+n-2r}\end{array}\right)$$
Writing an arbitrary $m+n$-row vector as $\mathbf{x}=(x_r, y_r, z_{m+n-2r})$ in terms of two $r$-vectors and an $m+n-2r$ vector, compute
$$\mathbf{x}\,\Upsilon_0\,\mathbf{x}^\prime = (x_r\mathbf{1}_r)^2 + (y_r\mathbf{1}_r)^2 + z_{m+n-2r}\,z_{m+n-2r}^\prime \ge 0,\tag{*}$$
showing $\Upsilon_0$ is positive semi-definite (this is the definition) and therefore $\Upsilon$ is positive semi-definite.
We may, however, write
$$\Upsilon = \left(\begin{array}{c|c} S & \mathbb{O}_{m\times n}\\ \hline \mathbb{O}_{n\times m} & T^\prime\end{array}\right)
\ \left(\begin{array}{c|c} S^{-1}A (S^\prime)^{-1} & B\\ \hline B^\prime & (T^\prime)^{-1} \Delta T^{-1}\end{array}\right)
\ \left(\begin{array}{c|c} S^\prime & \mathbb{O}_{m\times n}\\ \hline \mathbb{O}_{n\times m} & T\end{array}\right).$$
Name those three $m+n\times m+n$ matrices at the right $U,$ $\Sigma,$ and $U^\prime,$ respectively.  Recalling that $S$ and $T$ are invertible it follows $U$ is invertible, whence
$$\Sigma = U^{-1}\,\Upsilon\,(U^\prime)^{-1}.$$
Now $\Sigma$ is obviously positive semidefinite, because for any $m+n$ row vector $\mathbf{x},$
$$\mathbf{x}\,\Sigma\,\mathbf{x}^\prime = (\mathbf{x} U^{-1})\, \Upsilon\, (\mathbf{x}U^{-1})^\prime \ge 0$$
by virtue of $(*).$

$\Sigma$ solves the problem: it is a covariance matrix in which $B$ is the cross-covariance between the first $m$ and last $n$ variables.

In particular, let $X$ be the $m$-variate random variable and $Y$ the $n$-variate random variable.  Their variances and cross-covariance are
$$\operatorname{Var}(X) = S^{-1}A(S^\prime)^{-1};\quad \operatorname{Var}(Y) = (T^\prime)^{-1}\Delta T^{-1};\quad \operatorname{Cov}(X,Y) = B.$$

Example
Consider $$B=\Sigma_5 = \pmatrix{0&1&0 \\ 0&1&0 \\ 0&1&0}.$$  Row-reduction produces $S$ and then column-reduction of the result produces $T$ with
$$S=\pmatrix{1&0&0 \\ -1&1&0 \\ -1&0&1},\quad T=\pmatrix{0&1&0 \\ 1&0&0 \\ 0&0&1}$$
and $r=1.$  Therefore $A = \Delta = \mathbb{I}_3$ and
$$S^{-1}A(S^\prime)^{-1} = \pmatrix{1&1&1 \\ 1&2&1 \\ 1&1&2};\quad T^{-1}\Delta(T^\prime)^{-1} = \mathbb{I}_3.$$
Consequently
$$\Sigma= \pmatrix{1&1&1  &0&1&0  \\
1&2&1  &0&1&0 \\
1&1&2  &0&1&0 \\
0&0&0  &1&0&0 \\
1&1&1  &0&1&0 \\
0&0&0  &0&0&1}.$$
You can check (by computing eigenvalues, for instance) that this matrix is positive semi-definite and you can see that $B$ is the cross-covariance of the first three and last three variables.  Finally, the non-trivial upper $3\times 3$ matrix indicates there isn't any magical way to simplify the results of this analysis (as one might initially hope).
