Duplication and elimination matrices

In mathematics, especially in linear algebra and matrix theory, the duplication matrix and the elimination matrix are linear transformations used for transforming half-vectorizations of matrices into vectorizations or (respectively) vice versa.

Duplication matrix

The duplication matrix $D_n$ is the unique $n^2\times \frac{n(n+1)}{2}$ matrix which, for any $n\times n$ symmetric matrix $A$, transforms $\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{h}(A)$ into $\mathrm{v}\mathrm{e}\mathrm{c}(A)$:

$D_n\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{h}(A)=\mathrm{v}\mathrm{e}\mathrm{c}(A)$.

For the $2\times 2$ symmetric matrix $A=\left[\begin{array}{cc}a& b\\ b& d\end{array}\right]$, this transformation reads

$D_n\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{h}(A)=\mathrm{v}\mathrm{e}\mathrm{c}(A)⟹\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}a\\ b\\ d\end{array}\right]=\left[\begin{array}{c}a\\ b\\ b\\ d\end{array}\right]$

The explicit formula for calculating the duplication matrix for a $n\times n$ matrix is:

$D_n^T=\sum _{i\ge j}{u}_{ij}(\mathrm{v}\mathrm{e}\mathrm{c}{T}_{ij}{)}^T$

Where:

• $u_{ij}$ is a unit vector of order $\frac{1}{2}n(n+1)$ having the value $1$ in the position $(j-1)n+i-\frac{1}{2}j(j-1)$ and 0 elsewhere;
• $T_{ij}$ is a $n\times n$ matrix with 1 in position $(i,j)$ and $(j,i)$ and zero elsewhere

Here is a C++ function using Armadillo (C++ library):

arma::mat duplication_matrix(const int &n) {
    arma::mat out((n*(n+1))/2, n*n, arma::fill::zeros);
    for (int j = 0; j < n; ++j) {
        for (int i = j; i < n; ++i) {
            arma::vec u((n*(n+1))/2, arma::fill::zeros);
            u(j*n+i-((j+1)*j)/2) = 1.0;
            arma::mat T(n,n, arma::fill::zeros);
            T(i,j) = 1.0;
            T(j,i) = 1.0;
            out += u * arma::trans(arma::vectorise(T));
        }
    }
    return out.t();
}

Elimination matrix

An elimination matrix $L_n$ is a $\frac{n(n+1)}{2}\times n^2$ matrix which, for any $n\times n$ matrix $A$, transforms $\mathrm{v}\mathrm{e}\mathrm{c}(A)$ into $\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{h}(A)$:

$L_n\mathrm{v}\mathrm{e}\mathrm{c}(A)=\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{h}(A)$. 

By the explicit (constructive) definition given by (Magnus Neudecker), the $\frac{1}{2}n(n+1)$ by $n^2$ elimination matrix $L_n$ is given by

$L_n=\sum _{i\ge j}{u}_{ij}\mathrm{v}\mathrm{e}\mathrm{c}(E_{ij}{)}^T=\sum _{i\ge j}(u_{ij}\otimes e_j^T\otimes e_i^T),$

where $e_i$ is a unit vector whose $i$-th element is one and zeros elsewhere, and $E_{ij}=e_i{e}_j^T$.

Here is a C++ function using Armadillo (C++ library):

arma::mat elimination_matrix(const int &n) {
    arma::mat out((n*(n+1))/2, n*n, arma::fill::zeros);
    for (int j = 0; j < n; ++j) {
        arma::rowvec e_j(n, arma::fill::zeros);
        e_j(j) = 1.0;
        for (int i = j; i < n; ++i) {
            arma::vec u((n*(n+1))/2, arma::fill::zeros);
            u(j*n+i-((j+1)*j)/2) = 1.0;
            arma::rowvec e_i(n, arma::fill::zeros);
            e_i(i) = 1.0;
            out += arma::kron(u, arma::kron(e_j, e_i));
        }
    }
    return out;
}

For the $2\times 2$ matrix $A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$, one choice for this transformation is given by

$L_n\mathrm{v}\mathrm{e}\mathrm{c}(A)=\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{h}(A)⟹\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}a\\ c\\ b\\ d\end{array}\right]=\left[\begin{array}{c}a\\ c\\ d\end{array}\right]$.

References

• Magnus, Jan R.; Neudecker, Heinz (1980), "The elimination matrix: some lemmas and applications", SIAM Journal on Algebraic and Discrete Methods 1 (4): 422–449, doi:10.1137/0601049, ISSN 0196-5212, http://repository.uvt.nl/id/ir-uvt-nl:oai:wo.uvt.nl:153210 .
• Jan R. Magnus and Heinz Neudecker (1988), Matrix Differential Calculus with Applications in Statistics and Econometrics, Wiley. ISBN:0-471-98633-X.
• Jan R. Magnus (1988), Linear Structures, Oxford University Press. ISBN:0-19-520655-X

de:Eliminationsmatrix