Kronecker Sum Covariance Models

Why Add Covariance Contributions?

For an array of measurements, dependence can arise along more than one index. For example, measurements might be related across locations within each time point, and also across time points within each location. A separable product covariance represents a particular interaction between those two forms of dependence. An additive model instead allows the covariance contributions from the two axes to be summed.

This distinction affects which cell pairs are correlated, how marginal variances combine, and whether the model is scientifically plausible. We use a $p\times q$ random array $X$, with row index $i$ and column index $j$, and use row-stacking for vectorization: the entries of row 1 come first, then those of row 2, and so on.

Definition: Let $A$ be a symmetric positive semidefinite $p\times p$ matrix and $B$ a symmetric positive semidefinite $q\times q$ matrix. The additive Kronecker-sum covariance model is $$ \operatorname{Cov}(\operatorname{vec}_r(X))=A\otimes I_q+I_p\otimes B, $$ where $\operatorname{vec}_r$ denotes row-stacking and $I_m$ is the $m\times m$ identity matrix. Equivalently, for cell indices $i,k\in\{1,\ldots,p\}$ and $j,l\in\{1,\ldots,q\}$, $$ \operatorname{Cov}(X_{ij},X_{kl})=A_{ik}\,\mathbf{1}\{j=l\}+\mathbf{1}\{i=k\}\,B_{jl}. $$

The first term contributes covariance across the first index when the second index matches; the second contributes covariance across the second index when the first index matches. The model is additive because these contributions are summed in the covariance matrix. The distribution of $X$ need not be Gaussian: the covariance structure is defined whether or not a distributional assumption is added.

Reading Covariance From the Array Indices

The cellwise formula follows directly from the ordering convention. In row-stacked order, cell $(i,j)$ has vector position $(i-1)q+j$. The corresponding entry of $A\otimes I_q$ is $A_{ik}$ when $j=l$, and zero otherwise; the corresponding entry of $I_p\otimes B$ is $B_{jl}$ when $i=k$, and zero otherwise. Adding the entries gives the formula.

This means that if both indices differ, the additive model sets the covariance to zero. If only the first index differs, the covariance comes from $A$; if only the second differs, it comes from $B$. The variance of a cell is $A_{ii}+B_{jj}$. These are direct consequences of the model, not additional assumptions about the marginal variances.

Worked Example: Building a Small Additive Covariance Matrix

Let $p=2$, $q=3$, and take $$ A=\begin{pmatrix}2&0.5\\0.5&1\end{pmatrix}, \qquad B=\begin{pmatrix}1&0&0\\0&2&0\\0&0&3\end{pmatrix}. $$ The eigenvalues of $A$ are $(3+\sqrt{2})/2$ and $(3-\sqrt{2})/2$, both positive; $B$ is diagonal with positive entries. Thus both matrices are positive definite.

In row-stacked order, the covariance matrix is $$ A\otimes I_3+I_2\otimes B = \begin{pmatrix} 3&0&0&0.5&0&0\\ 0&4&0&0&0.5&0\\ 0&0&5&0&0&0.5\\ 0.5&0&0&2&0&0\\ 0&0.5&0&0&3&0\\ 0&0&0.5&0&0&4 \end{pmatrix}. $$ For example, $\operatorname{Var}(X_{12})=A_{11}+B_{22}=2+2=4$. The cells $X_{11}$ and $X_{21}$ have the same column index, so their covariance is $A_{12}=0.5$. By contrast, $X_{11}$ and $X_{22}$ differ in both indices, so their covariance is zero.

The displayed matrix is positive definite: its eigenvalues are all sums of an eigenvalue of $A$ and an eigenvalue of $B$, and each such sum is positive. This eigenvalue property is justified below.

Positive Semidefiniteness and Eigenvalues

The component matrices are usually constrained to be positive semidefinite so that each represents a valid covariance contribution. Under that condition, their Kronecker sum is positive semidefinite. It is positive definite exactly when neither component has a zero eigenvalue at the same time as the other.

Theorem: Suppose $A$ and $B$ are symmetric positive semidefinite matrices of dimensions $p\times p$ and $q\times q$. If their eigenvalues are $\lambda_1,\ldots,\lambda_p$ and $\mu_1,\ldots,\mu_q$, then the eigenvalues of $A\otimes I_q+I_p\otimes B$ are all the sums $\lambda_i+\mu_j$, for $1\leq i\leq p$ and $1\leq j\leq q$. In particular, the sum is positive definite if and only if $\lambda_{\min}(A)+\lambda_{\min}(B)>0$.

Proof. Since $A$ and $B$ are symmetric, choose orthonormal eigenvectors $u_i$ of $A$ and $v_j$ of $B$, with eigenvalues $\lambda_i$ and $\mu_j$. The vectors $u_i\otimes v_j$ form an orthonormal basis of the product space. By the Kronecker product identity, $$ (A\otimes I_q)(u_i\otimes v_j)=\lambda_i(u_i\otimes v_j), \qquad (I_p\otimes B)(u_i\otimes v_j)=\mu_j(u_i\otimes v_j). $$ Therefore $$ (A\otimes I_q+I_p\otimes B)(u_i\otimes v_j) =(\lambda_i+\mu_j)(u_i\otimes v_j). $$ This gives all $pq$ eigenvalues, because the product vectors form a basis. Since $A$ and $B$ are positive semidefinite, each sum is nonnegative. The smallest sum is $\lambda_{\min}(A)+\lambda_{\min}(B)$, so all sums are strictly positive exactly when that minimum is strictly positive. $\square$

Worked Example: Checking Positive Definiteness

Suppose $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ and $B=\operatorname{diag}(1,4,6)$. The eigenvalues of $A$ are $3$ and $1$; those of $B$ are $1,4,6$. The six eigenvalues of the Kronecker sum are therefore $$ 3+1,\ 3+4,\ 3+6,\ 1+1,\ 1+4,\ 1+6 =4,\ 7,\ 9,\ 2,\ 5,\ 7. $$ All are strictly positive, so the covariance matrix is positive definite. More generally, when both components are positive semidefinite, at least one must be positive definite for their Kronecker sum to be positive definite. If both have a zero eigenvalue, the sum has a zero eigenvalue.

Additive Dependence Versus Separable Dependence

A separable product model uses a covariance of the form $A\otimes B$ under the same row-stacking convention. Its cellwise covariance is $A_{ik}B_{jl}$: dependence along both axes can contribute simultaneously, including when both indices differ. The additive model instead sums axis-specific contributions. It sets covariance to zero for cells that differ in both indices, and it adds the two diagonal contributions to obtain a cell variance.

Neither structure is universally preferable. Additivity is useful when scientific reasoning supports separate sources of variation associated with the two axes, with each source operating independently of the other axis. A product model is more natural when the covariance between two cells is understood as the product of their similarities along each axis. Model choice should reflect the intended dependence pattern, not just which matrix form is more convenient.

Cell relationship	Additive model	Separable product model
Both indices differ	Covariance is zero	Covariance can be nonzero
Only the first index differs	Covariance comes from $A$	Covariance is multiplied by the matching diagonal entry of $B$
Only the second index differs	Covariance comes from $B$	Covariance is multiplied by the matching diagonal entry of $A$
Cell variance	$A_{ii}+B_{jj}$	$A_{ii}B_{jj}$

Worked Example: Contrasting Covariance Patterns

Let $$ A=\begin{pmatrix}2&0.5\\0.5&1\end{pmatrix}, \qquad B=\begin{pmatrix}1&0.4\\0.4&2\end{pmatrix}. $$ Both are positive definite: $A$ has positive leading entry and determinant $2(1)-(0.5)^2=1.75$; $B$ has positive leading entry and determinant $1(2)-(0.4)^2=1.84$.

Under the additive model, $X_{11}$ and $X_{22}$ differ in both indices, so $\operatorname{Cov}(X_{11},X_{22})=0$. Under the product model, the same covariance is $A_{12}B_{12}=0.5(0.4)=0.2$.

For cells in the same first-index position, the additive covariance is $\operatorname{Cov}(X_{11},X_{12})=B_{12}=0.4$; the product covariance is $A_{11}B_{12}=2(0.4)=0.8$. Their variances also differ: the additive model gives $\operatorname{Var}(X_{11})=A_{11}+B_{11}=2+1=3$, while the product model gives $A_{11}B_{11}=2(1)=2$. Thus these models express genuinely different assumptions, even with the same component matrices.

A Random-Effects Interpretation and a Common Pitfall

One way to understand the additive structure is to write $X=U+V$, where $U$ and $V$ are independent random arrays with $\operatorname{Cov}(\operatorname{vec}_r(U))=A\otimes I_q$ and $\operatorname{Cov}(\operatorname{vec}_r(V))=I_p\otimes B$. Independence makes the covariance of their sum the sum of their covariances. This representation explains the two contributions without requiring $X$ itself to be normally distributed.

Proof of the covariance addition: For any two cells, independence gives $\operatorname{Cov}(U_{ij}+V_{ij},U_{kl}+V_{kl}) =\operatorname{Cov}(U_{ij},U_{kl})+\operatorname{Cov}(V_{ij},V_{kl})$, because both cross-covariances are zero. The two component covariances are $A_{ik}\mathbf{1}\{j=l\}$ and $\mathbf{1}\{i=k\}B_{jl}$, respectively. Their sum is exactly the additive cellwise formula. $\square$

Common mistake: It is tempting to read “Kronecker sum” as though it were a product model with two factors, or to multiply the two axis-specific covariances when both indices differ. That is not the definition here. In the additive model, the two indicator conditions determine which terms contribute; when both indices differ, both indicators are zero. The product model has a different formula and can assign nonzero covariance to that pair.

There is also a useful interpretive caution: the additive model does not say that every pair sharing a row or column has the same covariance. The relevant entries of $A$ or $B$ determine those covariances. Nor does it imply that the full array has independent rows or columns. It specifies a particular covariance pattern, which can still create dependence across the array.

Key takeaway: In a Kronecker-sum covariance, the two axes contribute separate covariance terms. Cell pairs sharing one index receive the corresponding axis contribution; pairs sharing neither index have zero covariance. The eigenvalues are pairwise sums, making positive definiteness straightforward to check.

Check Your Understanding

Use the row-stacking convention and the additive cellwise covariance formula.

For $p=2$ and $q=3$, which component determines $\operatorname{Cov}(X_{12},X_{22})$, and what is the value in terms of matrix entries?
When is the covariance between $X_{ij}$ and $X_{kl}$ necessarily zero under the additive model?
If the component matrices are positive semidefinite and both singular, can their Kronecker sum be positive definite? Explain using its eigenvalues.
How does the product model’s covariance between cells differing in both indices compare with the additive model’s covariance?
Give a scientific situation in which separate additive contributions from two array axes might be more plausible than a product structure.