# Linear matrix maps for which positivity and complete positivity coincide

S. ter Horst  S. ter Horst, Department of Mathematics, Research Focus Area:
Pure and Applied Analytics, North-West University, Potchefstroom, 2531 South
Africa and DSI-NRF Centre of Excellence in Mathematical and Statistical
Sciences (CoE-MaSS<EMAIL_ADDRESS>and  A. Naudé  A. Naudé, Faculty
of Engineering and the Built Environment, Academic Development Unit,
University of the Witwatersrand, Johannesburg, 2000 South Africa and DSI-NRF
Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS)
<EMAIL_ADDRESS>
###### Abstract.

By the Choi matrix criteria it is easy to determine if a specific linear
matrix map is completely positive, but to establish whether a linear matrix
map is positive is much less straightforward. In this paper we consider
classes of linear matrix maps, determined by structural conditions on an
associated matrix, for which positivity and complete positivity coincide. The
basis of our proofs lies in a representation of $*$-linear matrix maps going
back to work of R.D. Hill which enables us to formulate a sufficient condition
in terms of surjectivity of certain bilinear maps.

###### Key words and phrases:

Positive maps, completely positive maps, Choi matrix, linear matrix maps

###### 2010 Mathematics Subject Classification:

Primary 15A69; Secondary 15A23, 15B48

This work is based on the research supported in part by the National Research
Foundation of South Africa (Grant Number 118513 and 127364).

##  1\. Introduction

Positive and completely positive matrix maps play a profound role in many
fields of mathematics as well as in mathematical physics, cf., [21, 19, 10, 9,
17, 15, 22, 13] and references given there. While the structure of the class
of completely positive matrix maps is much better understood and it is easy to
verify complete positivity via the Choi matrix criteria, the class of positive
matrix maps is much less studied and more intricate, in part because of the
existence of non-decomposable positive matrix maps, i.e., maps that are not
the sum of a completely positive and a completely co-positive map [11, 24,
22]. Moreover, recent work shows that there are many more positive maps than
completely positive maps [9], using the connection with multivariable
polynomials that are positive but not sums-of-squares, while other recent work
[1] focuses on explicit construction of positive maps that are not completely
positive. In the present paper we take a different approach and focus on
classes of linear maps for which positivity and complete positivity coincide.
As indicated, via the Choi matrix it is not difficult to determine whether a
specific linear map is completely positive. However, we want to consider this
question independent of specific maps, and determine classes of linear maps,
determined by certain structural properties, where this always happens. That
this phenomenon occurs for certain classes of matrix maps came out of our
study of certain interpolation problems, on which we will report in a separate
publication, where the solution criteria is to show that a certain matrix map
determined by the interpolation data is positive, but it turns out that
positivity in that case coincides with complete positivity, independently of
the data, so that the Choi matrix criteria is not only sufficient for the
existence of a solution, but also necessary.

Throughout this paper ${\mathbb{F}}={\mathbb{C}}$ or
${\mathbb{F}}={\mathbb{R}}$. To avoid confusion about transposes or adjoints,
symmetric and Hermitian matrices, etc., we shall use notation as if
${\mathbb{F}}={\mathbb{C}}$. We consider a linear matrix map

${\mathcal{L}}:{\mathbb{F}}^{q\times q}\to{\mathbb{F}}^{n\times n}.$ (1.1)

With ${\mathcal{L}}$ we associate two matrices, the Choi matrix ${\mathbb{L}}$
given by

${\mathbb{L}}=\left[{\mathbb{L}}_{ij}\right]\in{\mathbb{F}}^{nq\times nq},\ \
{\mathbb{L}}_{ij}={\mathcal{L}}\left(\mathcal{E}_{ij}^{(q)}\right)\in{\mathbb{F}}^{n\times
n}\ \ \mbox{for $i=1,\ldots,n,\,j=1,\ldots,q$},$ (1.2)

where $\mathcal{E}_{ij}^{(q)}$ is the standard basis element in
${\mathbb{F}}^{q\times q}$ with a 1 on position $(i,j)$ and zeros elsewhere,
and what we call the matricization of ${\mathcal{L}}$, which is the matrix
$L\in{\mathbb{F}}^{n^{2}\times q^{2}}$ determined by the linear map

$L:{\mathbb{F}}^{q^{2}}\to{\mathbb{F}}^{n^{2}},\quad
L\,\left(\operatorname{vec}_{q}(V)\right)=\operatorname{vec}_{n}\left({\mathcal{L}}(V)\right),\quad
V\in{\mathbb{F}}^{q\times q},$ (1.3)

where $\operatorname{vec}_{r\times s}:{\mathbb{F}}^{r\times
s}\to{\mathbb{F}}^{rs}$ is the vectorization operator, abbreviated to
$\operatorname{vec}_{r}$ in case $r=s$. Decompose $L$ as a block matrix

$L=\left[L_{ij}\right]\quad\mbox{with}\quad L_{ij}\in{\mathbb{F}}^{n\times
q}\quad\mbox{for $i=1,\ldots,n,\,j=1,\ldots,q$}.$ (1.4)

Then ${\mathbb{L}}$ and $L$ determine each other in the following way: The
$((j-1)q+i)$-th column of $L$ is given by
$\operatorname{vec}_{n}({\mathbb{L}}_{ij})$ and the $((j-1)n+i)$-th column in
${\mathbb{L}}$ is given by $\operatorname{vec}_{n\times q}(L_{ij})$. This
relation between ${\mathbb{L}}$ and $L$ corresponds to a matrix reordering
that appeared in [18], was further studied in [14] and rediscovered recently
in [16]; see Proposition 4.1 and Section 3 in [8] for further details.

The well-known Choi matrix criteria tells us that ${\mathcal{L}}$ is
completely positive if and only if ${\mathbb{L}}$ is positive semidefinite.
Following [9], we say that ${\mathcal{L}}$ is $*$-linear if
${\mathcal{L}}(V^{*})={\mathcal{L}}(V)^{*}$ for all $V\in{\mathbb{F}}^{q\times
q}$ (for ${\mathbb{F}}={\mathbb{C}}$ this corresponds with ${\mathcal{L}}$
mapping Hermitian matrices to Hermitian matrices), and it turns out that
$*$-linearity is equivalent to ${\mathbb{L}}$ being Hermitian. In particular,
all completely positive linear matrix maps are $*$-linear. Positivity of
${\mathcal{L}}$ corresponds to

$\left(z\otimes x\right)^{*}{\mathbb{L}}\left(z\otimes x\right)\geq
0\quad\mbox{for all}\quad x\in{\mathbb{F}}^{n}\text{ and
}z\in{\mathbb{F}}^{q}.$ (1.5)

In this paper we determine structural properties of ${\mathcal{L}}$,
formulated in terms of the matricization $L$, under which positivity of
${\mathcal{L}}$, that is, (1.5), is sufficient to conclude that ${\mathbb{L}}$
is positive semidefinite, and hence ${\mathcal{L}}$ completely positive, which
are independent of the precise linear map ${\mathcal{L}}$ (i.e., the entries
in $L$).

Set $m=\textup{rank\,}{\mathbb{L}}$. The relation between ${\mathbb{L}}$ and
$L$ explained above implies that $m$ corresponds to the maximum number of
linearly independent matrices among the block entries of $L$, that is,

$m=\dim\textup{span}\\{L_{ij}\colon
i=1,\ldots,n,\,j=1,...,q\\}\subset{\mathbb{F}}^{n\times q}.$

In particular, it is possible to select $m$ linearly independent block entries
of $L$. Our main result states that if one can choose these linearly
independent matrices to satisfy a certain condition and all other matrices are
equal, then positivity and complete positivity of ${\mathcal{L}}$ will
coinicde.

######  Theorem 1.1.

Let ${\mathcal{L}}$ in (1.1) be a $*$-linear map with matricization
$L=\left[L_{ij}\right]$ and Choi matrix ${\mathbb{L}}$. Set
$m=\textup{rank\,}{\mathbb{L}}$. Assume one can choose linearly independent
$L_{1},\ldots,L_{m}\in{\mathbb{F}}^{n\times q}$ among the block entries of
$L$, say $L_{k}=L_{i_{k}j_{k}}$ for $k=1,\ldots m$, in such a way that:

(C1) For each $k$ we have $j_{l}\neq j_{k}$ for each $l\neq k$ or $i_{l}\neq
i_{k}$ for each $l\neq k$. (1.6)

Assume further that all other block entries of $L$ are equal to a single
matrix $L_{0}$ in the span of $L_{1},\ldots,L_{m}$. Then ${\mathcal{L}}$ is
completely positive if and only if ${\mathcal{L}}$ is positive.

This theorem will be proved in Section 3.

The additional condition that all other matrices must be equal to a single
matrix $L_{0}$ is unfortunate and we do not know whether it can be removed.
However, in a few specific examples where (C1) holds and more than a single
matrix occurs among the remaining matrices we could still prove the result,
while we have not been able to produce a counterexample. Specifically, when
the independent matrices $L_{1},\ldots,L_{m}$ can be chosen so that they are
all in a single block column or in a single block row, then the result remains
valid without assumptions on the remaining block matrices in $L$, see
Proposition 3.26 below.

######  Question 1.2.

Does Theorem 1.1 remain true if the condition that the remaining block entries
$L_{ij}$ for $(i,j)\neq(i_{k},j_{k})$, $k=1,\ldots,m$ should be equal to a
single matrix $L_{0}$ is removed?

A specific subclass appears when one restricts to $L_{0}=0$, that is, when the
non-zero block entries of $L$ form a linearly independent set. For this case
the result is proved separately in Subsection 3.2 as a stepping stone to the
proof of Theorem 1.1. In this case condition (C1) corresponds to a condition
on the zero-pattern in the block matrix $L$. Theorem 1.1 only provides a
necessary condition for positive maps ${\mathcal{L}}$ to be completely
positive. In the case where $L_{0}=0$ we give an example (in Example 3.10
below) where the phenomenon still occurs, but (C1) does not hold. If matrices
other than $L_{0}=0$ are allowed, this need not happen, at least for
${\mathbb{F}}={\mathbb{R}}$, as follows from Example 4.1 below.

The basis for our proof of Theorem 1.1 is a type of representation of linear
matrix maps studied by R.D. Hill in [4, 5], which we will refer to as Hill
representations. These representations have the form

${\mathcal{L}}(V)=\sum_{k,l=1}^{m}{\mathbb{H}}_{kl}\,A_{k}VA_{l}^{*},\quad
V\in{\mathbb{F}}^{q\times q},$ (1.7)

for matrices $A_{1},\ldots,A_{m}\in{\mathbb{F}}^{n\times q}$. The matrix
${\mathbb{H}}=\left[{\mathbb{H}}_{kl}\right]_{k,l=1}^{m}\in{\mathbb{F}}^{m\times
m}$ is called the Hill matrix associated with the representation (1.7).
Moreover, we call the Hill representation (1.7) of ${\mathcal{L}}$ minimal if
$m$ is the smallest number of matrices $A_{k}$ that occurs in Hill
representations for ${\mathcal{L}}$, and it turns out that this smallest
number equals $\textup{rank\,}{\mathbb{L}}$. A detailed analysis of minimal
Hill representations was conducted in [8] and a review of the relevant results
from [8] will be given in Section 2.

If ${\mathcal{L}}$ is given by the minimal Hill representation (1.7), then the
Choi matrix factors as

${\mathbb{L}}=\widehat{A}^{*}{\mathbb{H}}\widehat{A}\quad\mbox{with
}\widehat{A}^{*}:=\begin{bmatrix}\operatorname{vec}_{n\times
q}\left(A_{1}\right)&\ldots&\operatorname{vec}_{n\times
q}\left(A_{m}\right)\end{bmatrix}\in{\mathbb{F}}^{nq\times m}$

and $\widehat{A}$ is a matrix with full row rank. As proved by Poluikis and
Hill in [18], it follows that complete positivity of ${\mathcal{L}}$
corresponds to positive definiteness of ${\mathbb{H}}$. Using our criteria for
positivity in (1.5) and the above factorisation of ${\mathbb{L}}$, it follows
that a positive map ${\mathcal{L}}$ is completely positive when the bilinear
map determined by the matrix $\widehat{A}$:

$(z,x)\mapsto\widehat{A}(z\otimes x),\quad
x\in{\mathbb{F}}^{n},\,z\in{\mathbb{F}}^{q}$ (1.8)

is surjective. In fact, surjectivity of this bilinear map is independent of
the choice of the Hill representation. To prove Theorem 1.1 we show that under
the conditions in the theorem the bilinear map (1.8) is surjective
independently of the choice of the linearly independent matrices
$L_{1},\ldots,L_{m}$ and the matrix $L_{0}$, which works for
${\mathbb{F}}={\mathbb{C}}$ and almost for ${\mathbb{F}}={\mathbb{R}}$. In
fact, for ${\mathbb{F}}={\mathbb{R}}$ with $L$ as in Theorem 1.1, the only
case where the bilinear map (1.8) is not surjective is when $L$ is of the form

$L=\begin{bmatrix}L_{0}&\cdots&L_{0}&L_{q}&L_{0}&\cdots&L_{0}\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
L_{0}&\cdots&L_{0}&L_{q+r-2}&L_{0}&\cdots&L_{0}\\\
L_{1}&\cdots&L_{s-1}&L_{0}&L_{s}&\cdots&L_{q-1}\\\
L_{0}&\cdots&L_{0}&L_{q+r-1}&L_{0}&\cdots&L_{0}\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
L_{0}&\cdots&L_{0}&L_{q+n-2}&L_{0}&\cdots&L_{0}\end{bmatrix}$

with $L_{0}=\sum_{k=1}^{q+n-2}\alpha_{k}L_{k}$ such that
$4\left(\sum_{k=1}^{q-1}\alpha_{k}\right)\left(\sum_{k=q}^{q+n-2}\alpha_{k}\right)>1$.
In this case, however, positivity and complete positivity still coincides,
which is proved by explicitly computing the range of the bilinear map (1.8).

Little appears to be known about the ranges of bilinear maps, and we suspect
that to resolve Question 1.2 a further study of surjectivity of bilinear maps
might be required. However, we also point out that surjectivity of the
associated bilinear maps (1.8) is not a necessary condition, as illustrated in
Example 3.10.

Together with the current introduction, the paper consists of three sections.
In Section 2 we recall some results on $*$-linear maps and minimal Hill
representations from [8] that will be used throughout the paper. The proof of
the main result, Theorem 1.1, will be given in Section 3 where we also prove
that positivity and complete positivity coincide in a few additional cases and
present various examples. Finally, in Section 4 we illustrate our results by
considering the case $n=q=2$.

We conclude this introduction with some words on notation and terminology and
a few elementary formulas which can be found in most advanced linear algebra
textbooks, cf., [6, 7, 23]. The standard $j$-th basis element in
${\mathbb{F}}^{n}$ is denoted by $e_{j}^{(n)}$ or simply $e_{j}$ when the
length is clear from the context. We write $\mathcal{E}_{ij}^{(n,m)}$ for the
standard basis element of ${\mathbb{F}}^{n\times m}$ with $1$ on position
$(i,j)$ and zeros elsewhere, i.e.,
$\mathcal{E}_{ij}^{(n,m)}=e_{i}^{(n)}e_{j}^{(m)T}$, abbreviated to
$\mathcal{E}_{ij}^{(n)}$ when $m=n$. With $\vec{\mathbf{1}}_{n}$ we indicate
the all-1 vector of length $n$ and with $\mathbb{1}_{n\times m}$ the all-1
matrix of size $n\times m$, so that $\mathbb{1}_{n\times
m}=\vec{\mathbf{1}}_{n}\vec{\mathbf{1}}_{m}^{T}$. Also here, we write
$\mathbb{1}_{n}$ for $\mathbb{1}_{n\times n}$. Furthermore, $I_{n}$ denotes
the $n\times n$ identity matrix and $P^{(n)}_{i,j}$ the permutation matrix of
size $n\times n$ that interchanges the $i$-th and $j$-th row/ column,
abbreviated to $P_{i,j}$ when there can be no confusion about the size.

For $A\in{\mathbb{F}}^{n\times m}$ we write $A^{T}$ for its transpose, $A^{*}$
for its adjoint, $\overline{A}$ for its complex conjugate, $\textup{Ker\,}{A}$
for its nullspace and $\textup{Im}\,A$ for its range. We write
${\mathcal{H}}_{n}$ for the $n\times n$ Hermitian matrices and
${\mathcal{S}}_{n}$ for the $n\times n$ symmetric matrices. For
${\mathbb{F}}={\mathbb{R}}$, of course, ${\mathcal{H}}_{n}$ and
${\mathcal{S}}_{n}$ coincide. With $A\geq 0$ (resp. $A>0$) we indicate that
$A$ is positive semidefinite (resp. positive definite). Occasionally we will
identify ${\mathbb{F}}^{n}$ with ${\mathbb{F}}^{n\times 1}$, so that matrix
operations can be applied to vectors in ${\mathbb{F}}^{n}$. The Kronecker
product of matrices $A=\left[a_{ij}\right]\in{\mathbb{F}}^{n\times m}$ and
$B\in{\mathbb{F}}^{k\times l}$ is defined as

$A\otimes B=\left[a_{ij}B\right]\in{\mathbb{F}}^{(nk)\times(ml)},$

and the Hadamard product of matrices
$A=\left[a_{ij}\right],B=\left[b_{ij}\right]\in{\mathbb{F}}^{n\times m}$ is
defined as

$A\circ B=\left[a_{ij}b_{ij}\right]\in{\mathbb{F}}^{n\times m}.$

The _vectorization_ of a matrix $T\in{\mathbb{F}}^{n\times m}$ is the vector
$\operatorname{vec}_{n\times m}{(T)}\in{\mathbb{F}}^{nm}$ defined as

$\operatorname{vec}_{n\times m}(T)=\sum_{j=1}^{m}\left(e_{j}^{(m)}\otimes
I_{n}\right)Te_{j}^{(m)}.$

Note that the vectorization operator $\operatorname{vec}_{n\times m}$ defines
an invertible linear map from ${\mathbb{F}}^{n\times m}$ onto
${\mathbb{F}}^{nm}$. If $m=n$ we just write $\operatorname{vec}_{n}$ and if
the sizes are clear from the context, the indices are often left out.
Moreover, we have

$\operatorname{vec}_{m\times
n}\left({\mathcal{E}}^{(m,n)}_{l,k}\right)=\operatorname{vec}_{m\times
n}\left(e_{l}^{(m)}e_{k}^{(n)^{T}}\right)=e_{k}^{(n)}\otimes
e_{l}^{(m)}=e_{(k-1)m+l}^{(nm)}.$ (1.9)

Finally, we define the canonical shuffle
${\mathfrak{C}}_{n}:{\mathbb{F}}^{n^{2}}\to{\mathbb{F}}^{n^{2}}$ which on pure
tensors is defined as

${\mathfrak{C}}_{n}(z\otimes x)=x\otimes z,$

and extended to ${\mathbb{F}}^{n^{2}}$ by linearity. Note that
${\mathfrak{C}}_{n}$ is a linear self-invertible map on ${\mathbb{F}}^{n^{2}}$
which also satisfies ${\mathfrak{C}}_{n}^{*}={\mathfrak{C}}_{n}$, the matrix
corresponding to ${\mathfrak{C}}$ is a signature matrix.

##  2\. Hill representations for $*$-linear matrix maps

Throughout this section ${\mathcal{L}}$ is a linear matrix map of the form

${\mathcal{L}}:{\mathbb{F}}^{q\times q}\to{\mathbb{F}}^{n\times n}.$ (2.1)

Recall that ${\mathcal{L}}$ is called $*$-linear when
${\mathcal{L}}(V^{*})={\mathcal{L}}(V)^{*}$ for each
$V\in{\mathbb{F}}^{q\times q}$. In this section we review some results on
$*$-linear matrix maps from [8] that will be used throughout the paper. In
particular, we will discuss so-called minimal Hill representations that go
back to the work of R.D. Hill in [4] and were further studied in [5, 18, 8].
All results presented here can be found in [8], or easily derived from results
obtained there. We start with some general observations about $*$-linear
matrix maps.

###  2.1. $*$-Linear matrix maps

Let $L$ and ${\mathbb{L}}$ be the matricization and Choi matrix associated
with the linear map ${\mathcal{L}}$, as defined in (1.3) and (1.2),
respectively. In that case ${\mathcal{L}}$ can be expressed in terms of $L$
and ${\mathbb{L}}$ via

${\mathcal{L}}(V)=\operatorname{vec}^{-1}\left(L\operatorname{vec}(V)\right),\quad
V\in{\mathbb{F}}^{q\times q}.$ (2.2)

and

${\mathcal{L}}(V)=\sum_{i,j=1}^{q}v_{ij}{\mathbb{L}}_{ij},\quad
V=[v_{ij}]\in{\mathbb{F}}^{q\times q}.$ (2.3)

The latter can also be written as

${\mathcal{L}}(V)=\left(\vec{\mathbf{1}}_{q}\otimes
I_{n}\right)^{T}\left({\mathbb{L}}\circ\left(V\otimes\mathbb{1}_{n\times
n}\right)\right)\left(\vec{\mathbf{1}}_{q}\otimes I_{n}\right).$ (2.4)

$*$-Linearity of ${\mathcal{L}}$ can be expressed in terms of $L$ and
${\mathbb{L}}$ as explained in the next result.

######  Theorem 2.1.

Let ${\mathcal{L}}$ be a linear map as in (2.1). Define
$L\in{\mathbb{F}}^{n^{2}\times q^{2}}$ by (1.3) and
${\mathbb{L}}\in{\mathbb{F}}^{nq\times nq}$ by (1.2). Then the following are
equivalent:

  * (i)

${\mathcal{L}}$ is $*$-linear;

  * (ii)

${\mathbb{L}}\in{\mathcal{H}}_{nq}$;

  * (iii)

${\overline{L}}={\mathfrak{C}}_{n}L{\mathfrak{C}}_{q}$.

Moreover, when $L$ is written as block matrix $L=\left[L_{ij}\right]$ with
$L_{ij}=\left[\ell^{ij}_{kl}\right]\in{\mathbb{F}}^{n\times q}$ then (iii)
(and hence (i) and (ii)) is equivalent to

$\ell_{kl}^{ij}={\overline{\ell}}_{ij}^{kl},\quad 1\leq i,k\leq n,\quad 1\leq
j,l\leq q.$ (2.5)

One way of interpreting (2.5) is that “structural properties of $L$ as a block
matrix reoccur at the level of the blocks.” See Subsection 6.1 in [8] for more
details and examples. We mention here two implications, using the notation of
Theorem 2.1:

  * (i)

We have $L_{ij}=0$ if and only if $\ell_{ij}^{kl}=0$ for all $k$ and $l$.

  * (ii)

We have $L_{ij}=L_{rs}$ for $(i,j)\neq(r,s)$ if and only if
$\ell^{kl}_{ij}=\ell^{kl}_{rs}$ for all $k$ and $l$.

Hence zero-structure in the block matrix structure of $L$ corresponds to the
same zero-structure in all blocks $L_{ij}$, and similarly for repeating
blocks. Thus, diagonal, upper triangular, lower triangular, Toeplitz, Hankel,
circulant, etc. structure at the block matrix level of $L$ reoccurs in the
blocks.

Recall that $P_{i,j}$ denotes the permutation matrix that interchanges the
$i$-th and $j$-th row/column and note that
$P_{i,j}=P_{i,j}^{*}=P_{i,j}^{T}=P_{i,j}^{-1}$. In the next lemma we describe
how permutations in ${\mathcal{L}}$ translate to $L$ and ${\mathbb{L}}$. The
identities follow directly from (2.2) and (2.3); see also Lemma 3.6 and
Corollary 3.7 in [8].

######  Lemma 2.2.

Let ${\mathcal{L}}$ in (2.1) be linear and define $L$ as in (1.3) and
${\mathbb{L}}$ as in (1.2). For $1\leq i_{1},i_{2},k_{1},k_{2}\leq n$, $1\leq
j_{1},j_{2},l_{1},l_{2}\leq q$ define the linear map
${\widetilde{{\mathcal{L}}}}:{\mathbb{F}}^{q\times q}\to{\mathbb{F}}^{n\times
n}$ via
${\widetilde{{\mathcal{L}}}}(V)=P_{k_{1},k_{2}}{\mathcal{L}}(P_{l_{1},l_{2}}VP_{j_{1},j_{2}})P_{i_{1},i_{2}}$
for all $V\in{\mathbb{F}}^{q\times q}$. Then the matricization $\widetilde{L}$
and Choi matrix ${\widetilde{{\mathbb{L}}}}$ associated with
${\widetilde{{\mathcal{L}}}}$ are given by

$\widetilde{L}=\left(P_{i_{1},i_{2}}\otimes
P_{k_{1},k_{2}}\right)L\left(P_{j_{1},j_{2}}\otimes P_{l_{1},l_{2}}\right)\
\mbox{ and }\ {\widetilde{{\mathbb{L}}}}=\left(P_{i_{1},i_{2}}\otimes
P_{j_{1},j_{2}}\right){\mathbb{L}}\left(P_{k_{1},k_{2}}\otimes
P_{l_{1},l_{2}}\right).$

In particular, when $i_{r}=k_{r}$, $j_{r}=l_{r}$ for $r=1,2$, it follows that
${\mathcal{L}}$ is $*$-linear (respectively positive or completely positive)
if and only if ${\widetilde{{\mathcal{L}}}}$ is $*$-linear (respectively
positive or completely positive).

###  2.2. Minimal Hill representations for $*$-linear maps

In [4, 5] R.D. Hill studied linear matrix maps ${\mathcal{L}}$ as in (2.1) of
the form

${\mathcal{L}}(V)=\sum_{k,l=1}^{m}{\mathbb{H}}_{kl}\,A_{k}VA_{l}^{*},\quad
V\in{\mathbb{F}}^{q\times q},$ (2.6)

for matrices $A_{1},\dots,A_{m}\in{\mathbb{F}}^{n\times q}$ and
${\mathbb{H}}=[{\mathbb{H}}_{kl}]_{k,l=1}^{m}\in{\mathbb{F}}^{m\times m}$. We
shall refer to (2.6) as a Hill representation of ${\mathcal{L}}$ and to
${\mathbb{H}}$ as the associated Hill matrix. In case $m$ is such that there
is no Hill representation of ${\mathcal{L}}$ with a smaller number of matrices
$A_{k}$, then we say that the Hill representation (2.6) is minimal. It turns
out that the minimal value of $m$ is $\textup{rank\,}{\mathbb{L}}$, and in the
sequel we shall restrict to minimal Hill representations, that is, we will
restrict to the case that

$m:=\textup{rank\,}\,{\mathbb{L}}.$

Note that in a minimal Hill representation (2.6) the matrices
$A_{1},\ldots,A_{m}$ must be linearly independent. The next theorem collects a
few of the main results from [5, 18], for ${\mathbb{F}}={\mathbb{C}}$, see [8]
for the general case.

######  Theorem 2.3.

The linear map ${\mathcal{L}}$ in (2.1) is $*$-linear if and only if
${\mathcal{L}}$ admits a (minimal) Hill representation with ${\mathbb{H}}$
Hermitian. Moreover, ${\mathcal{L}}$ is completely positive if and only if
${\mathcal{L}}$ admits a (minimal) Hill representation with ${\mathbb{H}}$
positive definite.

The next result shows how the matrices $L$ and ${\mathbb{L}}$ associated with
${\mathcal{L}}$ can be expressed in terms of a minimal Hill representation of
${\mathcal{L}}$.

######  Proposition 2.4.

Let ${\mathcal{L}}$ be a $*$-linear map as in (2.1) with a minimal Hill
representation (2.6). Then the matricization $L$ and Choi matrix
${\mathbb{L}}$ associated with ${\mathcal{L}}$ are given by

$L=\sum_{k,l=1}^{m}{\mathbb{H}}_{kl}\,{\overline{A}}_{k}\otimes
A_{l}\quad\mbox{and}\quad{\mathbb{L}}=\widehat{A}^{*}{\mathbb{H}}^{T}\widehat{A},$
(2.7)

with $\widehat{A}^{*}:=\begin{bmatrix}\operatorname{vec}_{n\times
q}\left(A_{1}\right)&\ldots&\operatorname{vec}_{n\times
q}\left(A_{m}\right)\end{bmatrix}\in{\mathbb{F}}^{nq\times m}$. Moreover,
$\widehat{A}$ has full row rank and
$\textup{Ker\,}\widehat{A}=\textup{Ker\,}{\mathbb{L}}$.

One of the main results in [8] is the following theorem which addressed the
question of which matrices $A_{1},\ldots,A_{m}$ can appear in a minimal Hill
representation for ${\mathcal{L}}$. Decompose the matricization
$L=\left[L_{ij}\right]$ of ${\mathcal{L}}$ as in (1.4). The relation between
$L$ and ${\mathbb{L}}$, cf., Proposition 4.1 in [8], implies that the columns
of ${\mathbb{L}}$ are vectorizations of the blocks $L_{ij}$ in $L$. Therefore,
we have

$m=\dim\textup{span}\\{L_{ij}\colon
i=1,\ldots,n,\,j=1,...,q\\}\subset{\mathbb{F}}^{n\times q}.$ (2.8)

######  Theorem 2.5.

Let ${\mathcal{L}}$ be a $*$-linear map as in (2.1) with a minimal Hill
representation (2.6). Decompose the matricization $L=\left[L_{ij}\right]$
associated with ${\mathcal{L}}$ as in (1.4). Then

$\textup{span}\\{A_{k}\colon k=1,\ldots,m\\}=\textup{span}\\{L_{ij}\colon
i=1,\ldots,n,\,j=1,...,q\\}.$ (2.9)

Moreover, for any choice of matrices
$A_{1},\ldots,A_{m}\in{\mathbb{F}}^{n\times q}$ which satisfy (2.9) there
exists a matrix ${\mathbb{H}}=[{\mathbb{H}}_{kl}]\in{\mathbb{F}}^{m\times m}$
so that ${\mathcal{L}}$ is given by the corresponding minimal Hill
representation (2.6).

The fact that all matrices $A_{1},\ldots,A_{m}$ satisfying (2.9) appear in a
minimal Hill representation of ${\mathcal{L}}$ can also be expressed in terms
of the matrix $\widehat{A}$, as in the following proposition; see [8,
Proposition 5.10].

######  Proposition 2.6.

Assume ${\mathcal{L}}$ as in (2.1) is $*$-linear and let $m$ be the rank of
the Choi matrix ${\mathbb{L}}$ associated with ${\mathcal{L}}$. Let
$\widehat{A}\in{\mathbb{F}}^{m\times nq}$ with
$\textup{Ker\,}\widehat{A}=\textup{Ker\,}{\mathbb{L}}$. Then $\widehat{A}$ has
full row rank, so that $\widehat{A}\widehat{A}^{*}$ is invertible, and we have
${\mathbb{L}}=\widehat{A}^{*}{\mathbb{H}}^{T}\widehat{A}$ with

${\mathbb{H}}^{T}=\left(\widehat{A}\widehat{A}^{*}\right)^{-1}\widehat{A}{\mathbb{L}}\widehat{A}^{*}\left(\widehat{A}\widehat{A}^{*}\right)^{-1}.$

In particular, ${\mathcal{L}}$ admits a minimal Hill representation (2.6) with
$A_{k}=\operatorname{vec}^{-1}_{n\times q}\left({\widehat{a}}_{k}^{T}\right)$,
$k=1,\ldots,m$, where ${\widehat{a}}_{k}$ is the $k$-th row of $\widehat{A}$.

Next we will recall a construction of a minimal Hill representation of
${\mathcal{L}}$ from [8] that will be important in the sequel. Select
$L_{1},\ldots,L_{m}\in{\mathbb{F}}^{n\times q}$ so that

$\textup{span}\\{L_{ij}\colon
i=1,\ldots,n,\,j=1,...,q\\}=\textup{span}\\{L_{k}\colon k=1,\ldots,m\\}.$
(2.10)

Then there exits scalars $\alpha^{ij}_{k},\beta_{ij}^{k}\in{\mathbb{F}}$ for
$i=1,\ldots,n$, $j=1,...,q$ and $k=1,\ldots,m$, so that

$L_{k}=\sum_{i=1}^{n}\sum_{j=1}^{q}\beta_{ij}^{k}L_{ij},\quad
L_{ij}=\sum_{k=1}^{m}\alpha^{ij}_{k}L_{k}.$ (2.11)

Now set

$A_{k}=\left[{\overline{\alpha}}_{k}^{ij}\right]\in{\mathbb{F}}^{n\times
q}\quad\text{and}\quad
B_{k}=\left[\beta_{ij}^{k}\right]\in{\mathbb{F}}^{n\times
q}\quad\text{for}\quad k=1,\ldots,m.$ (2.12)

Then we have

$L=\sum_{k=1}^{m}{\overline{A}}_{k}\otimes L_{k}\quad\mbox{and}\quad
L_{k}=\left(\vec{\mathbf{1}}_{n}\otimes
I_{n}\right)^{*}\left(\left(B_{k}\otimes\mathbb{1}_{n\times q}\right)\circ
L\right)\left(\vec{\mathbf{1}}_{q}\otimes I_{q}\right).$ (2.13)

Finally, we define the Hill matrix associated with the selection
$L_{1},\ldots,L_{m}$ as:

${\mathbb{H}}={\mathbb{H}}\left({\mathcal{L}};L_{1},\ldots,L_{m}\right):=\left[\vec{\mathbf{1}}_{n}^{*}\left(B_{k}\circ{\overline{L}}_{l}\right)\vec{\mathbf{1}}_{q}\right]_{k,l=1}^{m}\in{\mathbb{F}}^{m\times
m}.$ (2.14)

######  Theorem 2.7.

Let ${\mathcal{L}}$ be a $*$-linear map as in (2.1) and select matrices
$L_{1},\ldots,L_{m}\in{\mathbb{F}}^{n\times q}$ satisfying (2.10). Then
${\mathcal{L}}$ is given by the minimal Hill representation (2.6) with
$A_{1},\ldots,A_{m}$ as in (2.12) and ${\mathbb{H}}$ as in (2.14). Moreover,
all minimal Hill representations of ${\mathcal{L}}$ are obtained in this way.

Finally, the minimal Hill representation of a $*$-linear map ${\mathcal{L}}$
is unique up to an invertible $m\times m$ matrix, as explained in the next
result; see Theorem 5.9 in [8] for an explicit formula for the invertible
matrix $\Phi$.

######  Theorem 2.8.

Let the $*$-linear matrix map ${\mathcal{L}}$ in (2.1) be given by two minimal
Hill representations (2.6), one with Hill matrix ${\mathbb{H}}$ and associated
matrices $A_{1},\ldots,A_{m}$ and one with Hill matrix ${\mathbb{H}}^{\prime}$
and associated matrices $A^{\prime}_{1},\ldots,A^{\prime}_{m}$. Then there
exists an invertible matrix $\Phi\in{\mathbb{F}}^{m\times m}$ so that

$(\Phi^{*}\otimes I_{n})\begin{bmatrix}A_{1}\\\ \vdots\\\
A_{k}\end{bmatrix}=\begin{bmatrix}A^{\prime}_{1}\\\ \vdots\\\
A^{\prime}_{k}\end{bmatrix},\quad{\overline{\Phi}}^{*}\widehat{A}=\widehat{A}^{\prime},\quad{\mathbb{H}}=\Phi{\mathbb{H}}^{\prime}\Phi^{*},$

where $\widehat{A}$ and $\widehat{A}^{\prime}$ are the matrices associated
with $A_{1},\ldots,A_{m}$ and $A^{\prime}_{1},\ldots,A^{\prime}_{m}$ as in
Proposition 2.4, respectively.

##  3\. Positive linear matrix maps that are completely positive

In this section we prove our main result, Theorem 1.1, give several
illustrative examples and prove a few more independent cases where positivity
implies complete positivity. We start with some general observations, followed
by proofs of the main result under additional constraints, leading eventually
to a proof of the general case.

###  3.1. General observations

While it is easy to determine if a $*$-linear map is completely positive, via
the Choi matrix, for positivity this is much less straightforward. We start
this section with a necessary and sufficient criteria on the Choi matrix to
determine whether ${\mathcal{L}}$ is positive. The result is essentially
contained in Propositions 3.1 and 3.6 of [9]; we add a proof for completeness.

######  Proposition 3.1.

A $*$-linear map ${\mathcal{L}}$ as in (2.1) is positive if and only if the
Choi matrix ${\mathbb{L}}$ in (1.2) satisfies

$\left(z\otimes x\right)^{*}{\mathbb{L}}\left(z\otimes x\right)\geq
0\quad\mbox{for all}\quad x\in{\mathbb{F}}^{n}\text{ and
}z\in{\mathbb{F}}^{q},$

or equivalently,

$\left(I_{q}\otimes x\right)^{*}{\mathbb{L}}\left(I_{q}\otimes x\right)\geq
0\quad\mbox{for all}\quad x\in{\mathbb{F}}^{n}.$

###### Proof.

For $V=\left[v_{ij}\right]_{i,j=1}^{q}\in{\mathbb{F}}^{q\times q}$ and
$x\in{\mathbb{F}}^{n}$ we have

$\displaystyle x^{*}{\mathcal{L}}\left(V\right)x$
$\displaystyle=\sum_{i,j=1}^{q}x^{*}{\mathbb{L}}_{ij}xv_{ij}=\vec{\mathbf{1}}_{q}^{*}\left(\left(I_{q}\otimes
x^{*}\right){\mathbb{L}}\left(I_{q}\otimes x\right)\circ
V\right)\vec{\mathbf{1}}_{q}$
$\displaystyle=\textup{trace\,}\left(\left(I_{q}\otimes
x^{*}\right){\mathbb{L}}\left(I_{q}\otimes x\right){\overline{V}}\right).$

The map ${\mathcal{L}}$ is positive precisely when
$x^{*}{\mathcal{L}}\left(V\right)x\geq 0$ for all $x\in{\mathbb{F}}^{n}$ and
positive semidefinite $V\in{\mathbb{F}}^{q\times q}$, hence if and only if
$\textup{trace\,}(\left(I_{q}\otimes
x^{*}\right){\mathbb{L}}\left(I_{q}\otimes x\right)V)\geq 0$ for all
$x\in{\mathbb{F}}^{n}$ and positive semidefinite $V\in{\mathbb{F}}^{q\times
q}$. It now follows by Fejér’s theorem, cf., [6, Corollary 5.7.4], that
${\mathcal{L}}$ is positive if and only if $\left(I_{q}\otimes
x^{*}\right){\mathbb{L}}\left(I_{q}\otimes x\right)\geq 0$ for all
$x\in{\mathbb{F}}^{n}$. Since ${\mathcal{L}}$ is assumed to be $*$-linear, we
have ${\mathbb{L}}\in{\mathcal{H}}_{nq}$ so that $\left(I_{q}\otimes
x^{*}\right){\mathbb{L}}\left(I_{q}\otimes x\right)\in{\mathcal{H}}_{q}$ for
each $x\in{\mathbb{F}}^{n}$. Therefore, this works for both
${\mathbb{F}}={\mathbb{C}}$ and ${\mathbb{F}}={\mathbb{R}}$. ∎

Using Proposition 2.4 we see that

$\left(z\otimes x\right)^{*}{\mathbb{L}}\left(z\otimes x\right)=\left(z\otimes
x\right)^{*}\widehat{A}^{*}{\mathbb{H}}^{T}\widehat{A}\left(z\otimes
x\right)\quad\mbox{for all}\quad x\in{\mathbb{F}}^{n}\text{ and
}z\in{\mathbb{F}}^{q}.$

Thus, positivity of ${\mathcal{L}}$ in (2.1) is equivalent to
$y^{*}{\mathbb{H}}^{T}y\geq 0$ for all $y$ from the set

${\mathfrak{Y}}_{\widehat{A}}:=\\{y_{z,x}:=\widehat{A}(z\otimes x)\colon
x\in{\mathbb{F}}^{n},\,z\in{\mathbb{F}}^{q}\\},$ (3.1)

while complete positivity is equivalent to ${\mathbb{H}}\geq 0$ (or
equivalently ${\mathbb{H}}^{T}\geq 0$). Whether a positive map ${\mathcal{L}}$
is also completely positive thus depends on whether the set
${\mathfrak{Y}}_{\widehat{A}}$ contains enough vectors to conclude
${\mathbb{H}}\geq 0$ from the fact that $y^{*}{\mathbb{H}}^{T}y\geq 0$ for all
$y\in{\mathfrak{Y}}_{\widehat{A}}$. Clearly this is the case when
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

######  Corollary 3.2.

Let ${\mathcal{L}}$ be a positive $*$-linear map as in (2.1). Define
$\widehat{A}$ as in Proposition 2.4 and ${\mathfrak{Y}}_{\widehat{A}}$ as in
(3.1). Then ${\mathcal{L}}$ is completely positive in case
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$, with $m$ the rank of the Choi
matrix ${\mathbb{L}}$.

The condition ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ is only
sufficient, cf., Example 3.10 below. However, by looking for classes of
positive maps which always satisfy
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$, and hence are completely
positive, provides us with some classes where positivity automatically implies
complete positivity. In particular,
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ holds for the class considered
in our main result, Theorem 1.1, for ${\mathbb{F}}={\mathbb{C}}$, while for
${\mathbb{F}}={\mathbb{R}}$ there is only a single case where this is not the
case.

######  Remark 3.3.

The matrix $\widehat{A}$ depends on the choice of linearly independent
matrices $L_{1},\ldots,L_{m}$ satisfying (2.10). However, by Theorem 2.8, the
ranges of two sets ${\mathfrak{Y}}_{\widehat{A}}$ in (3.1) corresponding to
two choices of such matrices $L_{1},\ldots,L_{m}$ are connected via an
invertible map in ${\mathbb{F}}^{m\times m}$. Hence for the question whether
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$, the particular choice of
$L_{1},\ldots,L_{m}$ is not relevant. Naturally, for the question whether
${\mathcal{L}}$ is completely positive whenever ${\mathcal{L}}$ is positive,
the choice of $L_{1},\ldots,L_{m}$ is also not relevant.

######  Remark 3.4.

Note that $\textup{Im}\,\widehat{A}={\mathbb{F}}^{m}$, by Proposition 2.4, and
hence
$\textup{span}\,{\mathfrak{Y}}_{\widehat{A}}=\textup{Im}\,\widehat{A}={\mathbb{F}}^{m}$.
However, the map $(z,x)\mapsto y_{z,x}=\widehat{A}(z\otimes x)$ is bilinear
and it may well happen that its range is strictly contained in
$\textup{Im}\,\widehat{A}$. Not much appears to be known about the ranges of
bilinear maps. We have only been able to find [20]. Clearly, the range of such
maps is closed under scalar multiplication, $\lambda
y\in{\mathfrak{Y}}_{\widehat{A}}$ for all $y\in{\mathfrak{Y}}_{\widehat{A}}$
and $\lambda\in{\mathbb{F}}$, but not necessarily under addition. As a result
of this lack of clarity on the structure of ranges of bilinear maps, it is far
from straightforward when ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ will
occur.

As a consequence of Proposition 2.6, the question whether
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ depends only on the kernel of
the Choi matrix.

######  Corollary 3.5.

Let ${\mathcal{L}}$ and ${\mathcal{L}}^{\prime}$ be positive $*$-linear maps
as in (2.1) with Choi matrices ${\mathbb{L}}$ and ${\mathbb{L}}^{\prime}$,
respectively. Set $m=\textup{rank\,}{\mathbb{L}}$,
$m^{\prime}=\textup{rank\,}{\mathbb{L}}^{\prime}$ and define
${\mathfrak{Y}}_{\widehat{A}}$ and ${\mathfrak{Y}}_{\widehat{A}^{\prime}}$ as
in (3.1), with $\widehat{A}$ and $\widehat{A}^{\prime}$ as in Proposition 2.4.
Assume $\textup{Ker\,}{\mathbb{L}}\subset\textup{Ker\,}{\mathbb{L}}^{\prime}$.
If ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$, then
${\mathfrak{Y}}_{\widehat{A}^{\prime}}={\mathbb{F}}^{m^{\prime}}$.

###### Proof.

Note that
$\textup{Ker\,}{\mathbb{L}}\subset\textup{Ker\,}{\mathbb{L}}^{\prime}$ implies
$m\geq m^{\prime}$. Since for $\widehat{A}\in{\mathbb{F}}^{m\times nq}$ and
$\widehat{A}^{\prime}\in{\mathbb{F}}^{m^{\prime}\times nq}$ we can take any
matrices with $\textup{Ker\,}\widehat{A}=\textup{Ker\,}{\mathbb{L}}$ and
$\textup{Ker\,}\widehat{A}^{\prime}=\textup{Ker\,}{\mathbb{L}}^{\prime}$, by
Proposition 2.6, and thus, without loss of generality, we may assume the first
$m^{\prime}$ rows of $\widehat{A}$ coincide with the rows of
$\widehat{A}^{\prime}$. In that case

$y_{z,x}=\widehat{A}(z\otimes x)=\begin{bmatrix}\widehat{A}^{\prime}(z\otimes
x)\\\ *\end{bmatrix}=:\begin{bmatrix}y_{z,x}^{\prime}\\\ *\end{bmatrix},\quad
x\in{\mathbb{F}}^{n},\,z\in{\mathbb{F}}^{q},$

with $*$ indicating an unspecified vector. It follows that if
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$, i.e., any
$y\in{\mathbb{F}}^{m}$ is of the form $y_{z,x}$ for some
$x\in{\mathbb{F}}^{n},\,z\in{\mathbb{F}}^{q}$, then also
${\mathfrak{Y}}_{\widehat{A}^{\prime}}={\mathbb{F}}^{m^{\prime}}$. ∎

In the remainder of this section we will only consider the case where the
matrices $L_{1},\ldots,L_{m}$ are selected among the entries $L_{ij}$ of the
block matrix $L$ associated with ${\mathcal{L}}$. Say $L_{k}=L_{i_{k}j_{k}}$
for $k=1,\ldots,m$ for a selection of distinct pairs $(i_{k},j_{k})$ with
$i_{k}\in\\{1,\ldots,n\\}$ and $j_{k}\in\\{1,\ldots,q\\}$. With this selection
of pairs we associate the matrix

$E:=\begin{bmatrix}e_{\left(j_{1}-1\right)n+i_{1}}^{(nq)^{T}}\\\ \vdots\\\
e_{\left(j_{m}-1\right)n+i_{m}}^{(nq)^{T}}\end{bmatrix}\in{\mathbb{F}}^{m\times
nq}.$ (3.2)

Note that $E$ only depends on the positions of the matrices
$L_{1},\ldots,L_{m}$ in $L$ and not on the entries of the matrices
$L_{1},\ldots,L_{m}$. In the next lemma we specify what the matrix
$\widehat{A}$ looks like in this case.

######  Lemma 3.6.

Let ${\mathcal{L}}$ as in (2.1) be $*$-linear. Define $L$ as in (1.3) and
${\mathbb{L}}$ as in (1.2) and set $m=\textup{rank\,}\,{\mathbb{L}}$. Let
$L_{1},\ldots,L_{m}$ be a selection of $m$ linearly independent matrices among
the blocks $L_{ij}$ of $L$, say $L_{k}=L_{i_{k}j_{k}}$ for
$i_{k}\in\\{1,\ldots,n\\}$ and $j_{k}\in\\{1,...,q\\}$. Then the matrices
$A_{1},\ldots,A_{m}$ in (2.12), with $\alpha^{ij}_{k}$ as in (2.11), are given
by

$A_{k}=\mathcal{E}_{i_{k}j_{k}}^{(n,q)}+\sum_{\begin{subarray}{c}(i,j)\neq(i_{k},j_{k})\\\
k=1,\ldots,m\end{subarray}}\overline{\alpha}_{k}^{ij}\mathcal{E}_{ij}^{(n,q)}$

and the matrix $\widehat{A}$ defined in Proposition 2.4 is given by

$\displaystyle\widehat{A}$
$\displaystyle=\begin{bmatrix}\operatorname{vec}_{n\times
q}\left(\overline{A}_{1}\right)^{T}\\\ \vdots\\\ \operatorname{vec}_{n\times
q}\left(\overline{A}_{m}\right)^{T}\end{bmatrix}=E+\sum_{\begin{subarray}{c}(i,j)\neq(i_{k},j_{k})\\\
k=1,\ldots,m\end{subarray}}\alpha^{ij}e_{(j-1)n+i}^{(nq)^{T}}\ \mbox{ with }\
\alpha^{ij}=\begin{bmatrix}\alpha^{ij}_{1}\\\ \vdots\\\
\alpha^{ij}_{m}\end{bmatrix}\in{\mathbb{F}}^{m}.$

###### Proof.

Since $L_{i_{k}j_{k}}=L_{k}$ for each $k$, we have $\alpha^{i_{k}j_{k}}_{k}=1$
and $\alpha^{i_{k}j_{k}}_{l}=0$ for $l\neq k$. Including this in the formula
$A_{k}=\sum_{i=1}^{n}\sum_{j=1}^{q}{\overline{\alpha}}_{k}^{ij}{\mathcal{E}}_{ij}^{(n,q)}$
gives the formula for $A_{k}$.

Finally, making use of $\eqref{UnitVectId1}$ and the fact that the
vectorization operator is linear which means it preserves linear combinations,
yields the formula for $\widehat{A}$. ∎

Note that in the formula for $\widehat{A}$ the ’structural properties’ related
to the choice of $L_{1},\ldots,L_{m}$ (contained in $E$) are separated from
the additional data (in the form of the vectors $\alpha^{ij}$). Most of the
results we obtain in this section relate to a pattern determined by the choice
of the matrices $L_{1},\ldots,L_{m}$, that is, on the matrix $E$ in (3.2).
However, often there are many ways to choose the linearly independent matrices
$L_{1},\ldots,L_{m}$. Hence the interpretation of these results is that they
hold for linear maps ${\mathcal{L}}$ so that a selection of
$L_{1},\ldots,L_{m}$ among the block matrices in $L$ can be made which
satisfies the constraints.

######  Remark 3.7.

In addition to how the matrices $L_{1},\ldots,L_{m}$ are chosen among the
block entries of $L$, also the numbering of the chosen matrices has an effect
on $\widehat{A}$, to be precise, reordering the selected matrices, corresponds
to multiplying $\widehat{A}$ on the left with a permutation matrix. Less
straight forward is that we can also reorder the columns and rows of $L$ in
any way we want. This will effect the block matrix entries of $L$, who will
all have the same reordering of rows and columns as done at the level of the
block rows and columns, but for the question considered in the present paper
that is not relevant. That reordering of block rows and columns is indeed
allowed, provided the rows and columns of the blocks are reordered in the same
way, is a direct consequence of Lemma 2.2.

###  3.2. The case where $L_{ij}=0$ for all $(i,j)\neq(i_{k},j_{k})$.

In this subsection we consider the case where all non-zero blocks in $L$ are
linearly independent. In other words, we prove Theorem 1.1 with $L_{0}=0$. We
also include several examples. Now choose $L_{1},\ldots,L_{m}$ to be the non-
zero blocks in $L$, say $L_{k}=L_{i_{k}j_{k}}$ for $k=1,\ldots,m$, so that
$L_{ij}=0$ for all $(i,j)\neq(i_{k},j_{k})$ for all $k$. In this case, by
Lemma 3.6, $\widehat{A}=E$ with $E$ the matrix in (3.2). Note that

$E(z\otimes x)=\begin{bmatrix}x_{i_{1}}z_{j_{1}}\\\ \vdots\\\
x_{i_{m}}z_{j_{m}}\end{bmatrix},\quad
x\in{\mathbb{F}}^{n},\,z\in{\mathbb{F}}^{q}.$ (3.3)

The next proposition characterizes when
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ and provides a proof of
Theorem 1.1 in the case considered in this subsection.

######  Proposition 3.8.

Let ${\mathcal{L}}$ as in (2.1) be $*$-linear. Define $L$ as in (1.3) and
${\mathbb{L}}$ as in (1.2) and set $m=\textup{rank\,}\,{\mathbb{L}}$. Let
$L_{1},\ldots,L_{m}$ be a selection of $m$ linearly independent matrices among
the blocks $L_{ij}$ of $L$, say $L_{k}=L_{i_{k}j_{k}}$ for $k=1,\ldots,m$.
Assume $L_{ij}=0$ for all $i,j$ with $(i,j)\neq(i_{k},j_{k})$ for
$k=1,\ldots,m$. Then ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ holds if
and only if the following condition holds:

(C1) For each $k$ we have $j_{l}\neq j_{k}$ for each $l$ or $i_{l}\neq i_{k}$
for each $l$. (3.4)

In particular, in case ${\mathcal{L}}$ as in (2.1) is a positive $*$-linear
map such that its matricization $L$ has the above structure, then
${\mathcal{L}}$ is also completely positive.

The result follows directly from the following lemma, since $\widehat{A}=E$,
which will also be of use in the sequel.

######  Lemma 3.9.

For the matrix $E$ in (3.2) associated with a selection $L_{1},\ldots,L_{m}$
among the block entries of $L$ we have

${\mathfrak{E}}_{1}:=\\{E(z\otimes
x):z\in{\mathbb{F}}^{q},\,x\in{\mathbb{F}}^{n}\\}={\mathbb{F}}^{m}$ (3.5)

if and only if condition (C1) in (3.4) holds.

###### Proof.

We first prove the necessity of (C1). Assume (C1) does not hold. We show that
${\mathfrak{E}}_{1}\neq{\mathbb{F}}^{m}$. Since (C1) does not hold there
exists a $k$ and $l_{1},l_{2}\neq k$ so that $i_{k}=i_{l_{1}}$ and
$j_{k}=j_{l_{2}}$ (note that $l_{1}=l_{2}$ can occur). Now take
$y\in{\mathbb{F}}^{m}$ with $y_{k}=0$ but $y_{l_{1}}$ and $y_{l_{2}}$ are non-
zero. If $y$ were of the form $y=E(z\otimes x)$ for $z\in{\mathbb{F}}^{q}$ and
$x\in{\mathbb{F}}^{n}$, then $x_{i_{k}}z_{j_{k}}=y_{k}=0$ implies either
$x_{i_{k}}=0$ or $z_{j_{k}}=0$, but then also
$y_{l_{1}}=x_{i_{k}}z_{j_{l_{1}}}=0$ or $y_{l_{2}}=x_{i_{l_{2}}}z_{j_{k}}=0$,
in contradiction with our choice of $y$. Thus
${\mathfrak{E}}_{1}\neq{\mathbb{F}}^{m}$ cannot occur if (C1) does not hold.

Now we turn to the sufficiency of (C1). Hence, assume (C1) holds. Take
$y\in{\mathbb{F}}^{m}$. For each $k$, when $j_{l}\neq j_{k}$ for each $l$
(case 1), take $z_{j_{k}}=y_{k}$ and $x_{i_{k}}=1$, while in case $i_{l}\neq
i_{k}$ for each $l$ (case 2), take $z_{j_{k}}=1$ and $x_{i_{k}}=y_{k}$. Set
all unspecified entries of $x\in{\mathbb{F}}^{n}$ and $z\in{\mathbb{F}}^{q}$
equal to zero. The requirements (case 1 or case 2) guarantee that the entries
of $x$ and $z$ are only given one value. Indeed, assume for instance that
$i_{k}=i_{l}$ for some $k\neq l$ (this is how $x_{i_{k}}$ could get two
values). This means for both $k$ and $l$ that case 2 is not possible, hence
case 1 applies, which yields $x_{i_{k}}=1=x_{i_{l}}$. A similar arguments
holds when $j_{k}=j_{l}$. Moreover, it is clear that
$x_{i_{k}}z_{j_{k}}=y_{k}$ for each $k$. Hence $y=E(z\otimes x)$. It follows
that ${\mathfrak{E}}_{1}={\mathbb{F}}^{m}$. ∎

Already for $n=q=2$ two cases are excluded by (C1) in the setting considered
in this subsection. These are discussed in the next two examples. The first
shows that ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ is not a necessary
condition for a positive map to be completely positive in general.

######  Example 3.10.

Consider the case where $L$ is a $2\times 2$ upper triangular block matrix

$L=\begin{bmatrix}L_{1}&L_{2}\\\
0&L_{3}\end{bmatrix}=\begin{bmatrix}a_{1}&b_{1}&a_{2}&b_{2}\\\
0&c_{1}&0&c_{2}\\\ 0&0&a_{3}&b_{3}\\\
0&0&0&c_{3}\end{bmatrix}\in{\mathbb{F}}^{4\times 4}.$

The cases with $L$ a $2\times 2$ block matrix with $m=3$ and the zero block in
another position can be treated in a similar way, leading to the same
conclusion. The zeros in the left-lower entries of $L_{i}$ follow because we
want the associated map ${\mathcal{L}}$ to be $*$-linear, but this requirement
implies more. Indeed, we have

${\mathbb{L}}=\begin{bmatrix}a_{1}&0&a_{2}&a_{3}\\\ 0&0&0&0\\\
b_{1}&0&b_{2}&b_{3}\\\ c_{1}&0&c_{2}&c_{3}\end{bmatrix},$

and $*$-linearity is equivalent to ${\mathbb{L}}={\mathbb{L}}^{*}$, hence to
$a_{1},b_{2},c_{3}\in{\mathbb{R}}$ and
$a_{2}={\overline{b}}_{1},a_{3}={\overline{c}}_{1},b_{3}={\overline{c}}_{2}$.
Thus, assuming $*$-linearity, we have

$L=\begin{bmatrix}a_{1}&b_{1}&{\overline{b}}_{1}&b_{2}\\\ 0&c_{1}&0&c_{2}\\\
0&0&{\overline{c}}_{1}&{\overline{c}}_{2}\\\
0&0&0&c_{3}\end{bmatrix}\quad\mbox{and}\quad{\mathbb{L}}=\begin{bmatrix}a_{1}&0&{\overline{b}}_{1}&{\overline{c}}_{1}\\\
0&0&0&0\\\ b_{1}&0&b_{2}&{\overline{c}}_{2}\\\
c_{1}&0&c_{2}&c_{3}\end{bmatrix}$

with $a_{1},b_{2},c_{3}\in{\mathbb{R}}$. In this case we have

$\widehat{A}=E=\begin{bmatrix}1&0&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{bmatrix}\quad\mbox{and}\quad\widehat{A}(z\otimes
x)=\begin{bmatrix}x_{1}z_{1}\\\ x_{1}z_{2}\\\ x_{2}z_{2}\end{bmatrix},\quad
x,z\in{\mathbb{F}}^{2}.$

Confirming the result of Proposition 3.8, it follows that

${\mathfrak{Y}}_{\widehat{A}}=\\{y\in{\mathbb{F}}^{3}\colon y_{2}=0\
\Rightarrow\ y_{1}y_{2}=0\\}\neq{\mathbb{F}}^{3}.$

Despite the fact that ${\mathfrak{Y}}_{\widehat{A}}\neq{\mathbb{F}}^{3}$, we
claim that positivity of ${\mathcal{L}}$ implies complete positivity, as we
will prove now. Note that the positivity of ${\mathcal{L}}$ corresponds to

$(I_{2}\otimes x)^{*}{\mathbb{L}}(I_{2}\otimes
x)=\begin{bmatrix}a_{1}|x_{1}|^{2}&{\overline{x}}_{1}\left(x_{1}{\overline{b}}_{1}+x_{2}{\overline{c}}_{1}\right)\\\
x_{1}\left({\overline{x}}_{1}b_{1}+{\overline{x}}_{2}c_{1}\right)&x^{*}\left[\begin{smallmatrix}b_{2}&{\overline{c}}_{2}\\\
c_{2}&c_{3}\end{smallmatrix}\right]x\end{bmatrix}\geq 0,\quad
x\in{\mathbb{F}}^{2},$ (3.6)

in particular, that $\left[\begin{smallmatrix}b_{2}&{\overline{c}}_{2}\\\
c_{2}&c_{3}\end{smallmatrix}\right]\geq 0$. Assume ${\mathcal{L}}$ is
positive. We show ${\mathcal{L}}$ is also completely positive. Clearly (3.6)
implies $a_{1}\geq 0$.

Consider the case where $a_{1}=0$. Then (3.6) implies
${\overline{x}}_{1}\left(x_{1}{\overline{b}}_{1}+x_{2}{\overline{c}}_{1}\right)=0$
for all $x_{1},x_{2}\in{\mathbb{F}}$, hence $b_{1}=c_{1}=0$. In that case
${\mathbb{L}}\geq 0$ corresponds to
$\left[\begin{smallmatrix}b_{2}&{\overline{c}}_{2}\\\
c_{2}&c_{3}\end{smallmatrix}\right]\geq 0$, which we already established.
Hence, for the remainder we may assume $a_{1}>0$.

Note that for $x$ with $x_{1}=0$ (3.6) only tells us that $c_{3}\geq 0$, which
we already know. Thus only if $x_{1}\neq 0$ can we get new information. In
that case, without loss of generality we can take $x_{1}=1$ so that $x$ has
the form $x=\left[\begin{smallmatrix}1\\\ \delta\end{smallmatrix}\right]$ and
(3.6) reduces to

$\begin{bmatrix}a_{1}&{\overline{b}}_{1}+\delta{\overline{c}}_{1}\\\
b_{1}+{\overline{\delta}}c_{1}&b_{1}+\delta{\overline{c}}_{2}+{\overline{\delta}}c_{2}+|\delta|^{2}c_{3}\end{bmatrix}\geq
0.$

Since $a_{1}>0$, this is the same as positivity of the Schur complement with
respect to $a_{1}$, that is

$\displaystyle 0$ $\displaystyle\leq
a_{1}\left(b_{1}+\delta{\overline{c}}_{2}+{\overline{\delta}}c_{2}+|\delta|^{2}c_{3}\right)-\left({\overline{b}}_{1}+\delta{\overline{c}}_{1}\right)\left(b_{1}+{\overline{\delta}}c_{1}\right)$
$\displaystyle=\left(a_{1}b_{1}-|b_{1}|^{2}\right)+\delta\left(a_{1}{\overline{c}}_{2}-{\overline{c}}_{1}b_{1}\right)+{\overline{\delta}}\left(a_{1}c_{2}-c_{1}{\overline{b}}_{1}\right)+|\delta|^{2}\left(a_{1}c_{3}-|c_{1}|^{2}\right)$
(3.7) $\displaystyle=\begin{bmatrix}1\\\
\delta\end{bmatrix}^{*}\begin{bmatrix}a_{1}b_{1}-|b_{1}|^{2}&a_{1}{\overline{c}}_{2}-{\overline{c}}_{1}b_{1}\\\
{\overline{a}}_{1}c_{2}-c_{1}{\overline{b}}_{1}&a_{1}c_{3}-|c_{1}|^{2}\end{bmatrix}\begin{bmatrix}1\\\
\delta\end{bmatrix}.$

By scaling we obtain that

$x^{*}\begin{bmatrix}a_{1}b_{1}-|b_{1}|^{2}&a_{1}{\overline{c}}_{2}-{\overline{c}}_{1}b_{1}\\\
{\overline{a}}_{1}c_{2}-c_{1}{\overline{b}}_{1}&a_{1}c_{3}-|c_{1}|^{2}\end{bmatrix}x\geq
0$

for all $x\in{\mathbb{F}}^{2}$ with $x_{1}\neq 0$, while for $x_{1}=0$
(equivalently $a_{1}c_{3}-|c_{1}|^{2}\geq 0$) this follows by taking
$|\delta|$ large enough in (3.7). Hence, we conclude that

$\begin{bmatrix}a_{1}b_{1}-|b_{1}|^{2}&a_{1}{\overline{c}}_{2}-{\overline{c}}_{1}b_{1}\\\
{\overline{a}}_{1}c_{2}-c_{1}{\overline{b}}_{1}&a_{1}c_{3}-|c_{1}|^{2}\end{bmatrix}\geq
0,\mbox{ so that }\begin{bmatrix}0&0&0\\\
0&a_{1}b_{1}-|b_{1}|^{2}&a_{1}{\overline{c}}_{2}-{\overline{c}}_{1}b_{1}\\\
0&{\overline{a}}_{1}c_{2}-c_{1}{\overline{b}}_{1}&a_{1}c_{3}-|c_{1}|^{2}\end{bmatrix}\geq
0.$

The latter shows precisely that the Schur complement of ${\mathbb{L}}$ with
respect to $a_{1}$ is positive semidefinite, so that we can conclude that
${\mathbb{L}}\geq 0$, or equivalently, that ${\mathcal{L}}$ is completely
positive, as claimed.

######  Example 3.11.

Take

$L=\begin{bmatrix}L_{1}&L_{2}\\\
L_{3}&L_{4}\end{bmatrix}=\begin{bmatrix}\mathcal{E}_{11}^{(2)}&\mathcal{E}_{21}^{(2)}\\\
\mathcal{E}_{12}^{(2)}&\mathcal{E}_{22}^{(2)}\end{bmatrix}=\begin{bmatrix}1&0&0&0\\\
0&0&1&0\\\ 0&1&0&0\\\ 0&0&0&1\end{bmatrix}\in{\mathbb{F}}^{4\times 4}.$

Thus $n=q=2$ and $m=4$. In this case ${\mathbb{L}}={\mathbb{H}}=L=L^{-1}.$ In
particular, the Choi matrix ${\mathbb{L}}$ is Hermitian, but not positive
semidefinite, and hence the associated linear map ${\mathcal{L}}$ is
$*$-linear, but not completely positive. In fact, we have

${\mathcal{L}}(K)=\sum_{i,j=1}^{2}k_{ij}{\mathbb{L}}_{ij}=\begin{bmatrix}k_{11}&k_{21}\\\
k_{12}&k_{22}\end{bmatrix}=K^{T},\quad K=\begin{bmatrix}k_{11}&k_{12}\\\
k_{21}&k_{22}\end{bmatrix}\in{\mathbb{F}}^{2\times 2}.$

Hence, this choice of $L$ leads to the transpose map, which is one of the best
known examples of a positive linear map which is not completely positive.

In this case we have $\widehat{A}=E=L$, since $L_{1},\ldots,L_{4}$ are
linearly independent, and

${\mathfrak{Y}}_{\widehat{A}}=\left\\{\left[\begin{smallmatrix}x_{1}z_{1}\\\
x_{1}z_{2}\\\ x_{2}z_{1}\\\
x_{2}z_{2}\end{smallmatrix}\right]:\,x_{i},z_{i}\in{\mathbb{F}},\,i=1,2\right\\}.$

It is easily checked that
$\begin{bmatrix}0&1&1&0\end{bmatrix}^{T}\not\in{\mathfrak{Y}}_{\widehat{A}}$
so that ${\mathfrak{Y}}_{\widehat{A}}\neq{\mathbb{F}}^{4}$. Furthermore, for
$x,z\in{\mathbb{F}}^{2}$ we have

$(z\otimes x)^{*}{\mathbb{L}}(z\otimes
x)=\left({\overline{x}}_{1}z_{1}+{\overline{x}}_{2}z_{2}\right)\left({\overline{{\overline{x}}_{1}z_{1}+{\overline{x}}_{2}z_{2}}}\right)=|{\overline{x}}_{1}z_{1}+{\overline{x}}_{2}z_{2}|^{2}\geq
0,$

verifying that ${\mathcal{L}}$ is positive.

While there will be other choices of $L_{1},\ldots,L_{4}$ where the $*$-linear
map ${\mathcal{L}}$ associated with this choice is both positive and
completely positive, the example shows that the ‘structure’ imposed by the
positions of the linearly independent blocks does not guarantee it is always
the case.

In fact, if this ‘pattern’ is contained in a larger matrix $L$, then we can
also construct an example where the same phenomenon occurs.

######  Corollary 3.12.

Let $(i_{k},j_{k})$, for $k=1,\ldots,m$, be a selection of distinct points in
$\\{1,\ldots,n\\}\times\\{1,\ldots,q\\}$ so that there exist
$k_{1},\ldots,k_{4}$ with

$i_{k_{1}}=i_{k_{2}}\neq i_{k_{3}}=i_{k_{4}}\quad\mbox{and}\quad
j_{k_{1}}=j_{k_{3}}\neq j_{k_{2}}=j_{k_{4}}.$

Then there exists a selection of matrices
$L_{1},\ldots,L_{m}\in{\mathbb{F}}^{n\times q}$ so that the linear map
${\mathcal{L}}$ with matricization $L=\left[L_{ij}\right]$ determined by
$L_{i_{k}j_{k}}=L_{k}$, $k=1,\ldots,m$ and $L_{ij}=0$ for
$(i,j)\neq(i_{k},j_{k})$ for all $k$ is a $*$-linear positive map that is not
completely positive.

###### Proof.

The result is proved by embedding Example 3.11 into a larger matricization
$L$. Possibly after relabeling $L_{1},\ldots,L_{m}$ and reordering block rows
and columns in $L$ (see Remark 3.7) we can arrange to have $k_{l}=l$ for
$l=1,\ldots,4$ and $i_{1}<i_{3}$, $j_{1}<j_{2}$. Since we will construct a
case where $L_{ij}=0$ for $(i,j)\neq(i_{k},j_{k})$ for all $k$, we have that
$\widehat{A}=E$ so that $\widehat{A}$ depends only on the choice of the pairs
$(i_{k},j_{k})$. Moreover, $\widehat{A}$ has the form

$\displaystyle\widehat{A}=\begin{bmatrix}\widehat{A}_{0}\\\
\widehat{A}_{1}\end{bmatrix}=\begin{bmatrix}0&e^{(4)}_{1}&0&e^{(4)}_{3}&0&e^{(4)}_{2}&0&e^{(4)}_{4}&0\\\
\widehat{A}_{11}&0&\widehat{A}_{12}&0&\widehat{A}_{13}&0&\widehat{A}_{14}&0&\widehat{A}_{15}\end{bmatrix}\mbox{
with}$ $\displaystyle\hskip
56.9055pt\widehat{A}_{11}\in{\mathbb{F}}^{(m-4)\times((j_{1}-1)n+i_{1}-1)},\
\widehat{A}_{15}\in{\mathbb{F}}^{(m-4)\times((q-j_{2})n+n-i_{3})},$
$\displaystyle\widehat{A}_{12}\in{\mathbb{F}}^{(m-4)\times(i_{3}-i_{1}-1)},\,\widehat{A}_{13}\in{\mathbb{F}}^{(m-4)\times((j_{2}-j_{1})n+i_{1}-i_{3}-1)},\,\widehat{A}_{14}\in{\mathbb{F}}^{(m-4)\times(i_{3}-i_{1}-1)},$

and the $0$-s indicating zero matrices of appropriate size. For the Hill
matrix take

${\mathbb{H}}=\begin{bmatrix}{\mathbb{H}}_{0}&0\\\
0&{\mathbb{H}}_{1}\end{bmatrix}\quad\mbox{with}\ \
{\mathbb{H}}_{0}=\begin{bmatrix}\mathcal{E}_{11}^{(2)}&\mathcal{E}_{21}^{(2)}\\\
\mathcal{E}_{12}^{(2)}&\mathcal{E}_{22}^{(2)}\end{bmatrix}\in{\mathbb{F}}^{4\times
4},$

and ${\mathbb{H}}_{1}\in{\mathbb{F}}^{(m-4)\times(m-4)}$ any positive definite
matrix. Then ${\mathbb{L}}:=\widehat{A}^{*}{\mathbb{H}}^{T}\widehat{A}$ has
rank $m$, is selfadjoint but not positive semidefinite. Also, by construction,
$L$ has the required structure, which follows from the relation between
${\mathbb{L}}$ and $L$ explained in the introduction; see also [8, Proposition
4.1 & Section 3]. It follows that the linear map ${\mathcal{L}}$ associated
with ${\mathbb{L}}$ and $L$ is $*$-linear but not completely positive. To see
that ${\mathcal{L}}$ is positive, note that
${\mathbb{L}}=\widehat{A}_{0}^{*}{\mathbb{H}}_{0}^{T}\widehat{A}_{0}+\widehat{A}_{1}^{*}{\mathbb{H}}_{1}^{T}\widehat{A}_{1}$
with
${\mathbb{L}}_{1}:=\widehat{A}_{1}^{*}{\mathbb{H}}_{1}^{T}\widehat{A}_{1}$
positive semidefinite and
${\mathbb{L}}_{0}:=\widehat{A}_{0}^{*}{\mathbb{H}}_{0}^{T}\widehat{A}_{0}$ the
matrix ${\mathbb{L}}$ in Example 3.11 with zero-rows and zero-columns added.
Hence, if $(z\otimes x)^{*}{\mathbb{L}}_{0}(z\otimes x)\geq 0$ for all $z,x$,
then ${\mathcal{L}}$ is positive. Note that $\widehat{A}_{0}(z\otimes
x)=\begin{bmatrix}x_{i_{1}}z_{j_{1}}&x_{i_{1}}z_{j_{2}}&x_{i_{3}}z_{j_{1}}&x_{i_{3}}z_{j_{2}}\end{bmatrix}^{T}$,
hence the argument used in Example 3.11 also applies here, and it follows that
${\mathcal{L}}$ is positive indeed. ∎

While Example 3.10 shows that for $2\times 2$ block upper triangular $L$
positivity of the associated $*$-linear map ${\mathcal{L}}$ implies complete
positivity, Corollary 3.12 implies that for block upper triangular $L$ of
larger size this is not the case.

######  Example 3.13.

For $n=q>2$ it follows that there are matrices $L_{ij}\in{\mathbb{F}}^{n\times
n}$, for $i\leq j$, so that the linear map ${\mathcal{L}}$ with matricization
$L$ given by the block upper triangular matrix

$L=\begin{bmatrix}L_{11}&\cdots&\cdots&L_{1n}\\\ 0&\ddots&&\vdots\\\
\vdots&\ddots&\ddots&\vdots\\\ 0&\cdots&0&L_{nn}\end{bmatrix},$

where the non-zero blocks $L_{ij}$, $i\leq j$, are linearly independent, is
positive but not completely positive. Indeed, for $n=q>2$ the right upper
$2\times 2$ corner forms a $2\times 2$ block of linearly independent matrices.

###  3.3. The case where $L_{ij}=L_{0}$ for all $(i,j)\neq(i_{k},j_{k})$:
General setting.

Now we start with the general case of Theorem 1.1, i.e., where $L_{0}$ need
not be the zero matrix. Set

${\mathfrak{S}}:=\textup{span}\\{L_{ij}\colon i=1,\ldots,n,\,j=1,...,q\\}.$
(3.8)

Hence, we are assuming here that there exists a single matrix
$L_{0}\in{\mathfrak{S}}$ so that $L_{ij}=L_{0}$ for all
$(i,j)\neq(i_{k},j_{k})$ for $k=1,\ldots,m$. Although the case $L_{0}=0$ is
covered in the previous subsection, we do allow this as a possibility here
too. Since ${\mathfrak{S}}$ coincides with the span of $L_{1},\ldots,L_{m}$,
we can write $L_{0}=\sum_{k=1}^{m}\alpha_{k}L_{k}$ for
$\alpha_{1},\ldots,\alpha_{m}\in{\mathbb{F}}$, which are uniquely determined
by $L_{0}$, by the linear independence assumption. Note that in the case we
consider here $\alpha_{k}^{ij}=\alpha_{k}$ for $(i,j)\neq(i_{k},j_{k})$ for
all $k$ and it thus follows from Lemma 3.6 that

$\widehat{A}=E+\alpha v^{T}$

with

$\displaystyle E:=\begin{bmatrix}e_{\left(j_{1}-1\right)n+i_{1}}^{(nq)^{T}}\\\
\vdots\\\
e_{\left(j_{m}-1\right)n+i_{m}}^{(nq)^{T}}\end{bmatrix}\in{\mathbb{F}}^{m\times
nq},\quad\alpha:=\begin{bmatrix}\alpha_{1}\\\ \vdots\\\
\alpha_{m}\end{bmatrix}\in{\mathbb{F}}^{m},$
$\displaystyle\quad\text{and}\quad
v:=\vec{\mathbf{1}}_{nq}-\sum_{l=1}^{m}e_{\left(j_{l}-1\right)n+i_{l}}^{(nq)}=\vec{\mathbf{1}}_{nq}-E^{T}\vec{\mathbf{1}}_{m}\in{\mathbb{F}}^{nq}.$

The latter formula for $v$ shows that $\widehat{A}$ can also be written as

$\widehat{A}=E+\alpha\left(\vec{\mathbf{1}}_{nq}^{T}-\vec{\mathbf{1}}_{m}^{T}E\right)=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)E+\alpha\vec{\mathbf{1}}_{nq}^{T}.$
(3.9)

In view of the second formula for $\widehat{A}$ in (3.9) we collect here some
properties of the matrix $I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$.

######  Lemma 3.14.

The matrix $I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$ is invertible if and only if
$\sum_{k=1}^{m}\alpha_{k}\neq 1$, and in that case
$\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)^{-1}=I_{m}+\left(1-\sum_{k=1}^{m}\alpha_{k}\right)^{-1}\alpha\vec{\mathbf{1}}_{m}^{T}$.
In case $\sum_{k=1}^{m}\alpha_{k}=1$ we have

$\textup{Ker\,}I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}=\textup{span}\\{\alpha\\}\quad\mbox{and}\quad\left(\textup{Im}\,I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)^{\perp}=\textup{span}\left\\{\vec{\mathbf{1}}_{m}\right\\}.$

###### Proof.

The invertibility criteria and formula for the inverse follow directly from
the Sherman–Morrison formula [3]. In case $\sum_{k=1}^{m}\alpha_{k}=1$, since
$I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$ is a rank 1 perturbation of an
invertible matrix, the kernel and cokernel are of dimension 1. It is easily
verified that $\alpha$ is in
$\textup{Ker\,}I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$ and
$\vec{\mathbf{1}}_{m}\in\textup{Ker\,}\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)^{*}=\textup{Ker\,}I_{m}-\vec{\mathbf{1}}_{m}\alpha^{*}$,
which prove the formulas for the kernel and cokernel of
$I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$. ∎

In the next two subsections we shall provide a proof for Theorem 1.1 in the
case where $\sum_{k=1}^{m}\alpha_{k}\neq 1$ and the case where
$\sum_{k=1}^{m}\alpha_{k}=1$, respectively.

###  3.4. The case where $L_{ij}=L_{0}$ for all $(i,j)\neq(i_{k},j_{k})$ and
$\sum_{k=1}^{m}\alpha_{k}\neq 1$.

In view of the formula for ${\widehat{A}}$ given in (3.9), when
$I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$ is invertible, it turns out useful to
consider the subset of ${\mathfrak{E}}_{1}$ in (3.5) given by

${\mathfrak{E}}_{2}:=\\{E(z\otimes
x):z\in{\mathbb{F}}^{q},\,x\in{\mathbb{F}}^{n},\,\vec{\mathbf{1}}_{nq}^{T}(z\otimes
x)=0\\}.$ (3.10)

Note that

$\vec{\mathbf{1}}_{nq}^{T}(z\otimes
x)=\left(\sum_{j=1}^{q}z_{j}\right)\left(\sum_{i=1}^{n}x_{i}\right).$ (3.11)

Hence $\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=0$ holds if and only if
$\sum_{j=1}^{q}z_{j}=0$ or $\sum_{i=1}^{n}x_{i}=0$. We now characterise when
${\mathfrak{E}}_{2}$ is equal to ${\mathbb{F}}^{m}$.

######  Lemma 3.15.

We have ${\mathfrak{E}}_{2}={\mathbb{F}}^{m}$ if and only if (C1) in (3.4)
holds together with at least one of the following conditions:

  * (C2.1)

there exists a $i_{0}$ such that $i_{0}\neq i_{k}$ for all $k$;

  * (C2.2)

there exists a $j_{0}$ such that $j_{0}\neq j_{k}$ for all $k$;

  * (C2.3)

there exist distinct $k_{1},k_{2},k_{3},k_{4}$ such that
$i_{k_{1}}=i_{k_{2}}\neq i_{k_{3}}=i_{k_{4}}$;

  * (C2.4)

there exist distinct $k_{1},k_{2},k_{3},k_{4}$ such that
$j_{k_{1}}=j_{k_{2}}\neq j_{k_{3}}=j_{k_{4}}$;

  * (C2.5)

we have $i_{k}\neq i_{l}$ for all $k\neq l$ and in case $q=1$ we must have
$m\neq n$;

  * (C2.6)

we have $j_{k}\neq j_{l}$ for all $k\neq l$ and in case $n=1$ we must have
$m\neq q$;

  * (C2.7)

there exists a $k$ such that $i_{l}\neq i_{k}$ and $j_{l}\neq j_{k}$ holds for
all $l\neq k$ and $m>1$.

Furthermore, if (C1) holds and all seven conditions (C2.1)–(C2.7) do not hold,
then, possibly rearranging the indices of $L_{1},\ldots,L_{m}$, only one of
the following three cases can occur:

  * (i)

$q=1$ and $m=n$, which implies $L=\left[\begin{smallmatrix}L_{1}\\\ \vdots\\\
L_{n}\end{smallmatrix}\right]$;

  * (ii)

$n=1$ and $m=q$, which implies
$L=\left[\begin{smallmatrix}L_{1}&\cdots&L_{q}\end{smallmatrix}\right]$;

  * (iii)

$m=n+q-2$ with $n,q>2$ and there exist $1\leq r\leq n$, $1\leq s\leq q$ so
that $L$ takes the form

$L=\begin{bmatrix}L_{0}&\cdots&L_{0}&L_{q}&L_{0}&\cdots&L_{0}\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
L_{0}&\cdots&L_{0}&L_{q+r-2}&L_{0}&\cdots&L_{0}\\\
L_{1}&\cdots&L_{s-1}&L_{0}&L_{s}&\cdots&L_{q-1}\\\
L_{0}&\cdots&L_{0}&L_{q+r-1}&L_{0}&\cdots&L_{0}\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
L_{0}&\cdots&L_{0}&L_{q+n-2}&L_{0}&\cdots&L_{0}\end{bmatrix}.$

###### Proof.

First we prove the sufficiency of (C1) together with one of the conditions
(C2.1)–(C2.7). Hence assume (C1) holds. Then each $y\in{\mathbb{F}}^{m}$ is of
the form $y=E(z\otimes x)$ for some $z\in{\mathbb{F}}^{q}$ and
$x\in{\mathbb{F}}^{n}$, since ${\mathfrak{E}}_{1}={\mathbb{F}}^{m}$, by Lemma
3.9. Now, under each of the additional assumptions (C2.1)–(C2.7) we have to
show that we can in fact obtain $y=E(z\otimes x)$ with the additional
constraint $\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=0$, or, equivalently,
$\sum_{j=1}^{q}z_{j}=0$ or $\sum_{i=1}^{n}x_{i}=0$.

Assume (C2.1). Let $y\in{\mathbb{F}}^{m}$ be given as $y=E(z\otimes x)$ for
some $z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$. Let $i_{0}$ be such
that $i_{0}\neq i_{k}$ for all $k$. From (3.3) it follows that the validity of
$y=E(z\otimes x)$ holds independent of the value of $x_{i_{0}}$, so that
$x_{i_{0}}$ can be modified to have $\sum_{i=1}^{n}x_{i}=0$.

Assume (C2.2). This follows by an argument similar to that for Condition
(C2.1).

Assume (C2.4). Then there exist $r,s>1$ (but $r+s\leq n$) so that, possibly
after rearranging indices of $L_{1},\ldots,L_{m}$ as well as block rows and
columns in $L$ (see Remark 3.7), $j_{k}=1$ and $i_{k}=k$ for $k=1,\ldots,r$
and $j_{r+l}=2$ and $i_{r+l}=r+l$ for $l=1,\ldots,s$, while $j_{p}\neq 1,2$
whenever $p>r+s$. Since $(C1)$ holds, also $i_{p}\neq 1,\ldots,r+s$ for
$p>r+s$. Let $y\in{\mathbb{F}}^{m}$ be given as $y=E(z\otimes x)$ for some
$z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$. Then $y_{k}=x_{k}z_{1}$ for
$k=1,\ldots,r$ and $y_{r+l}=x_{r+l}z_{2}$ for $l=1,\ldots,s$ while
$z_{1},z_{2},x_{1},\ldots,x_{r+s}$ do not occur in the factorisations
$y_{p}=x_{i_{p}}z_{j_{p}}$ for $p>r+s$. We can now adjust $z_{1}$ and $z_{2}$
so that $z_{1},z_{2}\neq 0$ and $\sum_{j=1}^{q}z_{j}=0$ and then redefine
$x_{k}:=y_{k}/z_{1}$ for $k=1,\ldots,r$ and $x_{r+l}:=y_{r+l}/z_{2}$ for
$l=1,\ldots,s$ resulting in new vectors $x$ and $z$ so that still
$y=E(z\otimes x)$ while also $\sum_{j=1}^{q}z_{j}=0$.

Assume (C2.3). This follows by an argument similar to that for Condition
(C2.4).

Assume (C2.5). In this case, since $i_{k}\neq i_{l}$ for all $k\neq l$ we can
chose $x_{i_{1}},\ldots,x_{i_{m}}$ independent of one another. Also, we have
$m\leq n$. In case $q=1$ and $m\neq n$ we have $m<n$ and thus we are in case
(C2.1). Assume $q>1$. Let $y\in{\mathbb{F}}^{m}$. Now choose $z_{1}=1-q\neq 0$
and $z_{2}=\cdots=z_{q}=1$, so that $\sum_{j=1}^{q}z_{j}=0$ and all $z_{j}$
are non-zero, and take $x\in{\mathbb{F}}^{n}$ with $x_{i_{k}}=y_{k}/z_{j_{k}}$
for $k=1,\ldots,m$ with the other entries chosen arbitrarily. In this case we
have $y=E(z\otimes x)$ while also $\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=0$
because $\sum_{j=1}^{q}z_{j}=0$.

Assume (C2.6). This follows by an argument similar to that for Condition
(C2.5).

Assume (C2.7). Since all other cases are covered, we may assume these
conditions are not satisfied, in particular, assume (C2.5) and (C2.6) do not
hold. By excluding the case $m=1$, reasoning as for (C2.4), again after
possibly rearranging indices of $L_{1},\ldots,L_{m}$ as well as block columns
and rows in $L$ (see Remark 3.7), it follows that there exist $r,s>1$ (with
$r+s+1\leq m$) so that $i_{k}=k$ and $j_{k}=1$ for $k=1,\ldots,r$,
$i_{r+l}=r+1$ and $j_{r+l}=l+1$ for $l=1,\ldots,s$ and $i_{r+s+1}=r+2$,
$j_{r+s+1}=s+2$, while $i_{p}\neq 1,\ldots,r+2$ and $j_{p}\neq 1,\ldots,s+2$
for $p>r+s+1$. Let $y\in{\mathbb{F}}^{m}$ be given as $y=E(z\otimes x)$ for
some $z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$. Then
$y_{k}=x_{k}z_{1}$ for $k=1,\ldots,r$, $y_{r+l}=x_{r+1}z_{1+l}$ for
$l=1,\ldots,s$ and $y_{r+s+1}=x_{r+2}z_{s+2}$, while
$z_{1},\ldots,z_{s+2},x_{1},\ldots,x_{r+2}$ do not occur in the factorisations
$y_{p}=x_{i_{p}}z_{j_{p}}$ for $p>r+s+1$. We now adjust $x$ and $z$ depending
on whether $\sum_{j\neq s+2}z_{j}$ is zero or not. In case $\sum_{j\neq
s+2}z_{j}\neq 0$, we just need to change $z_{s+2}$ and $x_{r+2}$ to
$z_{s+2}:=-\sum_{j\neq s+2}z_{j}$ and $x_{r+2}:=-y_{r+s+1}/\left(\sum_{j\neq
s+2}z_{j}\right)$. In case $\sum_{j\neq s+2}z_{j}=0$, select a $a\neq
0,z_{1}$, and redefine $z_{s+2}:=a$, $x_{r+2}=y_{r+s+1}/a$,
$x_{k}:=y_{k}/(z_{1}-a)$ for $k=1,\ldots,r$ and change $z_{1}$ to $z_{1}-a$.
In both cases it is easy to verify that the adjusted vectors $x$ and $z$ still
satisfy $y=E(z\otimes x)$ while now also $\sum_{j=1}^{q}z_{j}=0$.

Now we prove the necessity claim. Since
${\mathfrak{E}}_{2}\subset{\mathfrak{E}}_{1}$, it is clear from Lemma 3.9 that
(C1) is a necessary condition for ${\mathfrak{E}}_{2}={\mathbb{F}}^{m}$ to
hold. Hence, assume (C1) holds. To prove necessity we show that in case the
conditions (C2.1)–(C2.7) all do not hold, then we do not have
${\mathfrak{E}}_{2}={\mathbb{F}}^{m}$. Hence assume the conditions
(C2.1)–(C2.7) do not hold.

As a first step we show that this corresponds to the cases (i)–(iii). It is
easily verified that the cases (i)–(iii) satisfy (C1) whilst not satisfying
any of (C2.1)–(C2.7). Conversely, assume (C1) holds and non of (C2.1)-(C2.7)
hold. This is equivalent to (C1) holding and the negation of each of
(C2.1)-(C2.7) being true, which are given by:

  * $\neg$(C2.1)

for all $i$ there exists a $k$ such that $i=i_{k}$;

  * $\neg$(C2.2)

for all $j$ there exists a $k$ such that $j=j_{k}$;

  * $\neg$(C2.3)

if there exists distinct $k_{1},k_{2},k_{3},k_{4}$ such that
$i_{k_{1}}=i_{k_{2}}$ and $i_{k_{3}}=i_{k_{4}}$, then
$i_{k_{1}}=i_{k_{2}}=i_{k_{3}}=i_{k_{4}};$

  * $\neg$(C2.4)

if there exists distinct $k_{1},k_{2},k_{3},k_{4}$ such that
$j_{k_{1}}=j_{k_{2}}$ and $j_{k_{3}}=j_{k_{4}}$, then
$j_{k_{1}}=j_{k_{2}}=j_{k_{3}}=j_{k_{4}};$

  * $\neg$(C2.5)

there exist $k\neq l$ such that $i_{k}=i_{l}$ or $q=1$ and $m=n$;

  * $\neg$(C2.6)

there exist $k\neq l$ such that $j_{k}=j_{l}$ or $n=1$ and $m=q$;

  * $\neg$(C2.7)

for all $k$ there exists a $l\neq k$ such that $i_{k}=i_{l}$ or $j_{k}=j_{l}$.

First assume we have $q=1$. By $\neg$(C2.1) it follows that necessarily $m=n$,
so that we are in case (i). Likewise, if $n=1$, then $L$ must be as in (ii).

In case $q=2$, because of $\neg$(C2.2), either (C2.3) or (C2.5) holds. Hence
$q=2$ cannot occur. Similarly, $n=2$ cannot occur.

In the case where $n>2$ and $q>2$, following $\neg$(C2.1) and $\neg$(C2.2) we
know every row and column of $L$ contain at least one $L_{k}$. Furthermore,
following $\neg$(C2.5) and $\neg$(C2.6) we know there is at least one row and
one column of $L$ that contain more than one $L_{k}$ and together with
$\neg$(C2.3) and $\neg$(C2.4) we know there can be at most one such row and
column. Lastly, considering $\neg$(C2.7) we have for every row or column of
$L$ more than one $L_{k}.$ Combining these requirements above, together with
(C1) allows for no other form of $L$ than that in (iii).

To complete the proof we show that in each of the cases (i)–(iii) we do not
have ${\mathfrak{E}}_{2}\neq{\mathbb{F}}^{m}$. In case (i), we have

$y=E\left(z\otimes x\right)=\begin{bmatrix}x_{1}z_{1}\\\ \vdots\\\
x_{n}z_{1}\end{bmatrix}.$

Thus we need $x_{i}\in{\mathbb{F}}$ to be free and $z_{1}\neq 0$ to get
${\mathfrak{E}}_{2}={\mathbb{F}}^{m}$, proving that we cannot ensure
${\mathfrak{E}}_{2}={\mathbb{F}}^{m}$ and $\sum_{i=1}^{n}x_{i}=0$ or
$z_{1}=0.$ In a similar manner it can be proven that case (ii) implies
${\mathfrak{E}}_{2}\neq{\mathbb{F}}^{m},$ by swapping the roles of $z_{j}$ and
$x_{i}$.

Finally, assume $L$ has the form as in case (iii). For $x\in{\mathbb{F}}^{n}$
and $z\in{\mathbb{F}}^{q}$ we have

$E(z\otimes
x)=\left[\begin{matrix}x_{r}z_{1}&\ldots&x_{r}z_{s-1}&x_{r}z_{s+1}&\ldots&x_{r}z_{q}\end{matrix}\right.\\\
\left.\begin{matrix}x_{1}z_{s}&\ldots&x_{r-1}z_{s}&x_{r+1}z_{s}&\ldots&x_{n}z_{s}\end{matrix}\right]^{T}.$

Since $q,n>2$ we can choose $y\in{\mathbb{F}}^{m}$ such that all entries of
$y$ are non-zero while $\sum_{j=1}^{q-1}y_{j}=0$ and
$\sum_{j=q}^{q+n-2}y_{j}=0$. Let $x\in{\mathbb{F}}^{n}$ and
$z\in{\mathbb{F}}^{q}$ such that $y=E(z\otimes x)$. Then all entries of $x$
and $z$ must be non-zero. Also, $0=\sum_{j=1}^{q-1}y_{j}=x_{r}\sum_{j\neq
s}z_{j}$. Since $x_{r}\neq 0$, we have $\sum_{j\neq s}z_{j}=0$. Therefore,
$\sum_{j=1}^{q}z_{j}=z_{s}\neq 0$. Similarly, from $\sum_{j=q}^{q+n-2}y_{j}=0$
one obtains that $\sum_{i=1}^{n}x_{i}=x_{r}\neq 0$. Hence
$y\neq{\mathfrak{E}}_{2}$. ∎

It is now easy to prove Theorem 1.1 when $\sum_{k=1}^{m}\alpha_{k}\neq 1$
under the additional condition that one of (C2.1)–(C2.7) given in Lemma 3.15
holds.

######  Lemma 3.16.

Assume (C1) in (3.4) holds together with one of (C2.1)–(C2.7) in Lemma 3.15.
For the matrix $L_{0}\in{\mathfrak{S}}$ let
$\alpha_{1},\ldots,\alpha_{m}\in{\mathbb{F}}$ so that
$L_{0}=\sum_{k=1}^{m}\alpha_{k}L_{k}$. Assume in addition that
$\sum_{k=1}^{m}\alpha_{k}\neq 1$. Then
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

###### Proof.

Let $y\in{\mathbb{F}}^{m}$. By Lemma 3.14 the matrix
$I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$ is invertible. Hence
$y=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right){\widehat{y}}$ for some
${\widehat{y}}\in{\mathbb{F}}^{m}$. By Lemma 3.15 we have
${\mathfrak{E}}_{2}={\mathbb{F}}^{m}$. Thus ${\widehat{y}}=E(z\otimes x)$ for
some $z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$ with
$\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=0$. This implies that

$\widehat{A}(z\otimes
x)=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}E\right)(z\otimes
x)+\alpha\vec{\mathbf{1}}_{nq}^{T}(z\otimes
x)=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}E\right){\widehat{y}}+0=y.$

Hence $y\in{\mathfrak{Y}}_{\widehat{A}}$. Thus
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$. ∎

Hence, by the last statement of Lemma 3.15, it remains to prove that
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ in the setting of the present
subsection for the cases (i), (ii) and (iii) of Lemma 3.15. For (i) and (ii)
this is already covered by Proposition 3.8, also when
$\sum_{k=1}^{m}\alpha_{k}=1$.

######  Lemma 3.17.

Assume $L$ is as in (i) or (ii) in Lemma 3.15. Then
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

###### Proof.

For both (i) and (ii) the block entries of $L$ are assumed to be linearly
independent and (C1) is satisfied, hence the claim follows from Proposition
3.8. ∎

Finally, we prove the claim for $L$ as in (iii) of Lemma 3.15. First we prove
a lemma that will also be of use when we consider the case where
$\sum_{k=1}^{m}\alpha_{k}=1$.

######  Lemma 3.18.

Assume $L$ is as in case (iii) of Lemma 3.15 and define $E$ as in (3.2). Then
for each $y^{\circ}\in{\mathbb{F}}^{m}$ and $x_{r},z_{s}\neq 0$ there exist
unique $x\in{\mathbb{F}}^{n}$ and $z\in{\mathbb{F}}^{q}$ so that
$y^{\circ}=E(z\otimes x)$ and so that $x_{r}$ and $z_{s}$ correspond to the
$r$-th and $s$-th components of $x$ and $z$, respectively. In that case, we
have

$\vec{\mathbf{1}}_{nq}^{T}(z\otimes
x)=\left(\frac{{\widetilde{y}}^{\circ}_{2}}{z_{s}}+x_{r}\right)\left(\frac{{\widetilde{y}}^{\circ}_{1}}{x_{r}}+z_{s}\right),\quad\mbox{where}\quad{\widetilde{y}}^{\circ}_{1}=\sum_{k=1}^{q-1}y^{\circ}_{k},\quad{\widetilde{y}}^{\circ}_{2}=\sum_{k=q}^{m}y^{\circ}_{k}.$
(3.12)

###### Proof.

The equation $y^{\circ}=E(z\otimes x)$ with $x_{r},z_{s}\neq 0$ implies that
$y^{\circ}_{k}=x_{r}z_{k}$, so that $z_{k}=y^{\circ}_{k}/x_{r}$, for
$k=1,\ldots,s-1;$ $y^{\circ}_{k}=x_{r}z_{k+1}$, so that
$z_{k+1}=y^{\circ}_{k}/x_{r}$, for $k=s,\ldots,q-1$;
$y^{\circ}_{q-1+k}=x_{k}z_{s}$, so that $x_{k}=y^{\circ}_{q-1+k}/z_{s}$, for
$k=1,\ldots,r-1$ and $y^{\circ}_{q-1+k}=x_{k+1}z_{s}$, so that
$x_{k+1}=y^{\circ}_{q-1+k}/z_{s}$, for $k=r,\ldots,n-1$. Hence, $x$ and $z$
exist and are uniquely determined by $y^{\circ}$ and $x_{r},z_{s}$, as
claimed. Moreover, we have

$\sum_{i=1}^{n}x_{i}=\sum_{i=1}^{r-1}x_{i}+x_{r}+\sum_{i=r+1}^{n}x_{i}=\sum_{k=1}^{n-1}\frac{y^{\circ}_{q-1+k}}{z_{s}}+x_{r}=\frac{{\widetilde{y}}^{\circ}_{2}}{z_{s}}+x_{r},$

and a similar computation shows that
$\sum_{j=1}^{q}z_{j}=\frac{{\widetilde{y}}^{\circ}_{1}}{x_{r}}+z_{s}$. Then
(3.12) follows directly from (3.11). ∎

######  Lemma 3.19.

Assume $L$ is as in case (iii) of Lemma 3.15 and $\sum_{k=1}^{m}\alpha_{k}\neq
1$. Then for ${\mathbb{F}}={\mathbb{C}}$ we have
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{C}}^{m}$, while for
${\mathbb{F}}={\mathbb{R}}$ we have
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{R}}^{m}$ if and only if

$4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}\leq
1,\quad\mbox{with}\quad{\widetilde{\alpha}}_{1}=\sum_{k=1}^{q-1}\alpha_{k},\
{\widetilde{\alpha}}_{2}=\sum_{k=q}^{m}\alpha_{k}.$ (3.13)

Moreover, in case $4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}>1$, we
have

${\mathfrak{Y}}_{\widehat{A}}=\left\\{y\in{\mathbb{R}}^{m}\colon\sum_{k=1}^{q-1}y_{k}\neq
0\mbox{ or }\sum_{k=q}^{m}y_{k}\neq 0,\mbox{ or
}\sum_{k=1}^{q-1}|y_{k}|=0,\mbox{ or }\sum_{k=q}^{m}|y_{k}|=0\right\\}.$

###### Proof.

Assume $L$ has the form as in case (iii) in Lemma 3.15 and
$\sum_{k=1}^{m}\alpha_{k}\neq 1$. Fix a $y\in{\mathbb{F}}^{m}$. In this case
the matrix $I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$ is invertible, by Lemma
3.14, and hence for each $\lambda\in{\mathbb{F}}$ we can find a unique
$y_{\lambda}^{\circ}=y^{\circ}\in{\mathbb{F}}^{m}$ so that

$y-\alpha\lambda=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y^{\circ},\quad\mbox{that
is}\quad
y=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y^{\circ}+\alpha\lambda.$

Now write $y^{\circ}=E(z\otimes x)$ with $x_{r},z_{s}\neq 0$ so that $x$ and
$z$ are uniquely determined by $y^{\circ}$ and $x_{r},z_{s}$, that is, by
$y,\lambda,x_{r},z_{s}$, and formula (3.12) applies. Define
${\widetilde{\alpha}}_{1}$ and ${\widetilde{\alpha}}_{2}$ as in (3.13) and set

$\displaystyle{\widetilde{\alpha}}=\sum_{k=1}^{m}\alpha_{k},\quad{\widetilde{y}}=\sum_{k=1}^{m}y_{k},\quad{\widetilde{y}}_{1}=\sum_{k=1}^{q-1}y_{k},\quad{\widetilde{y}}_{2}=\sum_{k=q}^{m}y_{k}.$
(3.14)

Using the inversion formula from Lemma 3.14 we obtain that

$\displaystyle y^{\circ}$
$\displaystyle=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)^{-1}\left(y-\lambda\alpha\right)=\left(I_{m}+(1-{\widetilde{\alpha}})^{-1}\alpha\vec{\mathbf{1}}_{m}^{T}\right)\left(y-\lambda\alpha\right)$
$\displaystyle=\left(y-\lambda\alpha\right)+\frac{{\widetilde{y}}-\lambda{\widetilde{\alpha}}}{1-{\widetilde{\alpha}}}\alpha=y+\frac{-\lambda(1-{\widetilde{\alpha}})+{\widetilde{y}}-\lambda{\widetilde{\alpha}}}{1-{\widetilde{\alpha}}}\alpha=y+\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}}\alpha.$

Therefore, we have that

${\widetilde{y}}_{1}^{\circ}=\sum_{k=1}^{q-1}y_{k}^{\circ}={\widetilde{y}}_{1}+\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}}{\widetilde{\alpha}}_{1}\quad\mbox{and}\quad{\widetilde{y}}_{2}^{\circ}=\sum_{k=q}^{m}y_{k}^{\circ}={\widetilde{y}}_{2}+\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}}{\widetilde{\alpha}}_{2}.$

We now show how the variables $\lambda,x_{r},z_{s}$, subject to
$x_{r},z_{s}\neq 0$, can be chosen in such a way that
$\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=\lambda$, that is, using (3.12), that

$\left(\frac{{\widetilde{y}}_{2}+\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}}{\widetilde{\alpha}}_{2}}{z_{s}}+x_{r}\right)\left(\frac{{\widetilde{y}}_{1}+\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}}{\widetilde{\alpha}}_{1}}{x_{r}}+z_{s}\right)=\lambda.$
(3.15)

Set $\rho:=\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}},$ so that
$\lambda=\rho\left({\widetilde{\alpha}}-1\right)+{\widetilde{y}}$. Note that
varying $\lambda$ in ${\mathbb{F}}$, $\rho$ obtains all values in
${\mathbb{F}}$ as well. Then (3.15) translates to

$\displaystyle\rho\left({\widetilde{\alpha}}-1\right)+{\widetilde{y}}$
$\displaystyle=\left(\frac{{\widetilde{y}}_{2}+\rho{\widetilde{\alpha}}_{2}}{z_{s}}+x_{r}\right)\left(\frac{{\widetilde{y}}_{1}+\rho{\widetilde{\alpha}}_{1}}{x_{r}}+z_{s}\right)$
$\displaystyle=\frac{\left({\widetilde{y}}_{2}+\rho{\widetilde{\alpha}}_{2}\right)\left({\widetilde{y}}_{1}+\rho{\widetilde{\alpha}}_{1}\right)}{z_{s}x_{r}}+{\widetilde{y}}_{2}+\rho{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{1}+\rho{\widetilde{\alpha}}_{1}+z_{s}x_{r}$
$\displaystyle=\frac{\left({\widetilde{y}}_{2}+\rho{\widetilde{\alpha}}_{2}\right)\left({\widetilde{y}}_{1}+\rho{\widetilde{\alpha}}_{1}\right)}{z_{s}x_{r}}+\rho{\widetilde{\alpha}}+{\widetilde{y}}+z_{s}x_{r}.$

Multiplying with $z_{s}x_{r}$ on both sides and rearranging terms this yields

$(z_{s}x_{r})^{2}+\rho
z_{s}x_{r}+\left({\widetilde{y}}_{2}+\rho{\widetilde{\alpha}}_{2}\right)\left({\widetilde{y}}_{1}+\rho{\widetilde{\alpha}}_{1}\right)=0.$
(3.16)

For ${\mathbb{F}}={\mathbb{C}}$ it is easy to find a $\rho$ so that the above
equation in $z_{s}x_{r}$ has a non-zero solution, after which it remains to
factor this solution to obtain non-zero $z_{s}$ and $x_{r}$ so that (3.15)
holds.

For ${\mathbb{F}}={\mathbb{R}}$, to obtain a non-zero real solution we need to
find $\rho$ so that in addition

$\left(1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}\right)\rho^{2}-4\left({\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1}\right)\rho-4{\widetilde{y}}_{1}{\widetilde{y}}_{2}=\rho^{2}-4\left({\widetilde{y}}_{2}+\rho{\widetilde{\alpha}}_{2}\right)\left({\widetilde{y}}_{1}+\rho{\widetilde{\alpha}}_{1}\right)>0,$

or the left-hand side of the inequality equal to 0 for a $\rho\neq 0$. Thus,
the question is whether

$f(\rho)=(1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2})\rho^{2}-4({\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1})\rho-4{\widetilde{y}}_{1}{\widetilde{y}}_{2}$
(3.17)

attains positive values or is equal to zero at a non-zero point $\rho$. We
consider three cases.

#### Case 1

Assume $1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}>0$. In this case
$f$ is a polynomial of degree two with positive main coefficient, hence
positive values are attained for $|\rho|$ large enough.

#### Case 2

Assume $1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}=0$. Then
${\widetilde{\alpha}}_{1}$ and ${\widetilde{\alpha}}_{2}$ are non-zero and of
the same sign. If
${\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1}\neq
0$, then $f$ is a polynomial of degree one and thus positive values are
attained. In case
${\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1}=0$,
$f$ is a constant function and two situations can occur: (1)
${\widetilde{y}}_{1}={\widetilde{y}}_{2}=0$ in which case $f$ is the zero-
function so that for $\rho$ we can take any non-zero value, and (2)
${\widetilde{y}}_{1},{\widetilde{y}}_{2}\neq 0$ with ${\widetilde{y}}_{1}$ and
${\widetilde{y}}_{2}$ of opposite sign (since ${\widetilde{\alpha}}_{1}$ and
${\widetilde{\alpha}}_{2}$ have the same sign) in which case the value of $f$
is $-4{\widetilde{y}}_{1}{\widetilde{y}}_{2}>0$ so that $\rho$ can be taken
arbitrarily.

#### Case 3

Finally, assume $1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}<0$. In
this case $f$ is a polynomial of degree two with a negative main coefficient.
Also ${\widetilde{\alpha}}_{1}$ and ${\widetilde{\alpha}}_{2}$ are non-zero
and of the same sign. We need to show that in this case
${\mathfrak{Y}}_{\widehat{A}}$ is as stated.

First consider $y\in{\mathbb{R}}^{m}$ with ${\widetilde{y}}_{1}$ and
${\widetilde{y}}_{2}$ not both zero. The maximum of $f$ is attained at
$\rho_{0}=2\left({\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1}\right)/\left(1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}\right)$.
Note that when $\rho_{0}=0$, that is, when
${\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1}=0$,
since ${\widetilde{\alpha}}_{1},{\widetilde{\alpha}}_{2}\neq 0$ and have the
same sign, ${\widetilde{y}}_{1},{\widetilde{y}}_{2}\neq 0$ and have opposite
signs, so that $f(\rho_{0})=f(0)=-4{\widetilde{y}}_{1}{\widetilde{y}}_{2}>0$.
Therefore, it sufficed to show that $f(\rho_{0})\geq 0$. This occurs when

$({\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1})^{2}+{\widetilde{y}}_{1}{\widetilde{y}}_{2}(1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2})\geq
0.$

Since $1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}<0$, the inequality
clearly holds when ${\widetilde{y}}_{1}{\widetilde{y}}_{2}\leq 0$. On the
other hand, for ${\widetilde{y}}_{1}{\widetilde{y}}_{2}>0$ we have

$\displaystyle({\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}+{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1})^{2}+{\widetilde{y}}_{1}{\widetilde{y}}_{2}(1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2})=$
$\displaystyle\qquad\qquad=({\widetilde{y}}_{1}^{2}{\widetilde{\alpha}}_{2}^{2}+2{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}{\widetilde{y}}_{1}{\widetilde{y}}_{2}+{\widetilde{y}}_{2}^{2}{\widetilde{\alpha}}_{1}^{2}+{\widetilde{y}}_{1}{\widetilde{y}}_{2}-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}{\widetilde{y}}_{1}{\widetilde{y}}_{2})$
$\displaystyle\qquad\qquad=({\widetilde{y}}_{1}{\widetilde{\alpha}}_{2}-{\widetilde{y}}_{2}{\widetilde{\alpha}}_{1})^{2}+{\widetilde{y}}_{1}{\widetilde{y}}_{2}>0.$

Hence $y\in{\mathfrak{Y}}_{\widehat{A}}$ when ${\widetilde{y}}_{1}\neq 0$ or
${\widetilde{y}}_{2}\neq 0$.

Next take $y\in{\mathbb{R}}^{m}$ with
${\widetilde{y}}_{1}={\widetilde{y}}_{2}=0$, so that also ${\widetilde{y}}=0$,
but not all summands in ${\widetilde{y}}_{1}$ and ${\widetilde{y}}_{2}$ are
zero. Such $y$ exist and we now show they are not in
${\mathfrak{Y}}_{\widehat{A}}$. Assume to the contrary that there exist
$x\in{\mathbb{R}}^{n}$ and $z\in{\mathbb{R}}^{q}$ so that

$y=\widehat{A}(z\otimes
x)=\left(I_{m}+\alpha\vec{\mathbf{1}}_{m}^{T}\right)E(z\otimes
x)+\alpha\vec{\mathbf{1}}_{nq}^{T}(z\otimes x).$

Set

$y^{\circ}:=E(z\otimes
x)\quad\mbox{and}\quad\lambda:=\vec{\mathbf{1}}_{nq}^{T}(z\otimes
x)\quad\mbox{so that}\quad
y=\left(I_{m}+\alpha\vec{\mathbf{1}}_{m}^{T}\right)y^{\circ}+\alpha\lambda.$

To use Lemma 3.18 we need to show that $x_{r}$ and $z_{s}$ are non-zero.
Following the computations in the first part of the proof we have

$y^{\circ}=y+\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}}\alpha=y-\frac{\lambda}{1-{\widetilde{\alpha}}}\alpha.$

First consider the case where $\lambda=0$. Then $y^{\circ}=y$ and since not
all summands in ${\widetilde{y}}_{1}$ and ${\widetilde{y}}_{2}$ are zero it
follows that $x_{r}$ and $z_{s}$ are non-zero. Thus Lemma 3.18 applies,
including (3.12) which leads to (3.15) that further specifies to

$0=\lambda=\left(\frac{0}{z_{s}}+x_{r}\right)\left(\frac{0}{x_{r}}+z_{s}\right)=x_{r}z_{s}.$

However, this identity cannot hold since $x_{r},z_{s}\neq 0$, hence $\lambda$
cannot be zero.

Since $\lambda\neq 0$, for $i=1,2$ we have
${\widetilde{y}}^{\circ}_{i}={\widetilde{y}}_{i}-\frac{{\widetilde{y}}-\lambda}{1-{\widetilde{\alpha}}}{\widetilde{\alpha}}_{i}=-\frac{\lambda}{1-{\widetilde{\alpha}}}{\widetilde{\alpha}}_{i}\neq
0$, because ${\widetilde{\alpha}}_{i}\neq 0$. Thus, not all summands in
${\widetilde{y}}^{\circ}_{1}$ and ${\widetilde{y}}^{\circ}_{2}$ are zero so
that we again obtain that $x_{r},z_{s}\neq 0$ and that Lemma 3.18 applies.
Then, as shown above, via (3.12) we obtain that (3.15) holds which implies
$z_{s}x_{r}$ is a non-zero solution to (3.16). This in turn means that
$f(\rho)$ in (3.17) must attain a positive value or zero at a number $\rho\neq
0$. However, in the case considered here
$f(\rho)=(1-4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2})\rho^{2}$ which
is zero at $\rho=0$ and negative for all other values of $\rho$. Hence
$y\not\in{\mathfrak{Y}}_{\widehat{A}}$.

Finally, it remains to consider the case where
${\widetilde{y}}_{1}={\widetilde{y}}_{2}=0$ and $y_{1}=\cdots=y_{q-1}=0$ or
$y_{q}=\cdots=y_{m}=0$. Say $y_{1}=\cdots=y_{q-1}=0$, the other case goes
similarly. Although ${\mathfrak{E}}_{2}$ in $\eqref{fE2}$ is not equal to
${\mathbb{R}}^{m}$ in this case, we claim that $y\in{\mathfrak{E}}_{2}$.
Indeed, take $x_{r}=0$ and $z_{s}$ so that $x_{k}$ for $k\neq r$ are all
determined by $y=E(z\otimes x)$, but the numbers $z_{k}$ for $k\neq s$ are
free to be chosen, so that we can easily arrange $\sum_{k=1}^{q}z_{k}=0$
leading to $\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=0$. Hence
$y\in{\mathfrak{E}}_{2}$, as claimed. Note further that
$y=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y$, since
$\vec{\mathbf{1}}_{m}^{T}y={\widetilde{y}}=0$. Therefore, for $x$ and $z$ as
above we have

$\widehat{A}(z\otimes
x)=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)E(z\otimes
x)+\alpha\vec{\mathbf{1}}_{nq}^{T}(z\otimes
x)=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y=y.$

Hence $y\in{\mathfrak{Y}}_{\widehat{A}}$. ∎

Although ${\mathfrak{Y}}_{\widehat{A}}\neq{\mathbb{R}}^{m}$ in case (iii) with
${\mathbb{F}}={\mathbb{R}}$ and
$4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}>1$, the explicit
computation of ${\mathfrak{Y}}_{\widehat{A}}$ in this case still enables us to
prove that positivity and complete positivity coincide in this case.

######  Lemma 3.20.

Assume $L$ is as in case (iii) of Lemma 3.15 and $\sum_{k=1}^{m}\alpha_{k}\neq
1$. Then ${\mathcal{L}}$ is positive if and only if ${\mathcal{L}}$ is
completely positive.

###### Proof.

By Lemma 3.19 we need only consider the case where ${\mathbb{F}}={\mathbb{R}}$
and $4{\widetilde{\alpha}}_{1}{\widetilde{\alpha}}_{2}>1$. We need to show
that $y^{T}{\mathbb{H}}y\geq 0$ for all $y\in{\mathfrak{Y}}_{\widehat{A}}$
implies ${\mathbb{H}}\geq 0$, where ${\mathbb{H}}$ is the Hill matrix
associated with the choice of $L_{1},\ldots,L_{m}$. Let
$y\not\in{\mathfrak{Y}}_{\widehat{A}}$. Then
${\widetilde{y}},{\widetilde{y}}_{1},{\widetilde{y}}_{2}$ in (3.14) satisfy
${\widetilde{y}}={\widetilde{y}}_{1}={\widetilde{y}}_{2}=0$. Then for $\mu\neq
0$ we have $y+\mu(e_{1}+e_{m})\in{\mathfrak{Y}}_{\widehat{A}}$ so that

$\displaystyle
y^{T}{\mathbb{H}}y+\mu\left(\left(e_{1}+e_{m}\right)^{T}{\mathbb{H}}y+y^{T}{\mathbb{H}}\left(e_{1}+e_{m}\right)\right)+\mu^{2}\left(e_{1}+e_{m}\right)^{T}{\mathbb{H}}\left(e_{1}+e_{m}\right)=$
$\displaystyle\qquad\qquad\qquad=\left(y+\mu\left(e_{1}+e_{m}\right)\right)^{T}{\mathbb{H}}\left(y+\mu\left(e_{1}+e_{m}\right)\right)\geq
0.$

Since this inequality holds for each $\mu\neq 0$, it must also hold for
$\mu=0$, so that also $y^{T}{\mathbb{H}}y\geq 0$ for
$y\not\in{\mathfrak{Y}}_{\widehat{A}}$ and we can conclude that
${\mathbb{H}}\geq 0$. ∎

###  3.5. The case where $L_{ij}=L_{0}$ for all $(i,j)\neq(i_{k},j_{k})$ and
$\sum_{k=1}^{m}\alpha_{k}=1$.

Next we consider the case where $\sum_{k=1}^{m}\alpha_{k}=1$, so that the
matrix $I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}$ is not invertible. We
distinguish between the case where ${\mathfrak{E}}_{2}$ in (3.10) is equal to
${\mathbb{F}}^{m}$, so that (C1) and one of (C2.1)–(C2.7) holds, and the case
where (C1) holds but ${\mathfrak{E}}_{2}\neq{\mathbb{F}}^{m}$, so that $L$
must be as in (i), (ii) or (iii) in Lemma 3.15. For $L$ as in (i) and (ii) the
result is already proved in Lemma 3.17. The remaining cases are proved in a
series of lemmas; in some of the proofs the condition
$\sum_{k=1}^{m}\alpha_{k}=1$ is not required, while in others it is.

######  Lemma 3.21.

Assume condition (C1) in (3.4) together with (C2.1) or (C2.2) holds. Then
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

###### Proof.

We give a proof for the case where (C1) and (C2.2) holds. The case where
(C2.2) is replaced by (C2.1) is proved analogously.

By assumption there exists a $j_{0}$ such that $j_{k}\neq j_{0}$ for all $k$.
This implies that $E\left(be_{j_{0}}\otimes x\right)=0$ for all
$b\in{\mathbb{F}}$ and all $x\in{\mathbb{F}}^{n}$. Let $y\in{\mathbb{F}}^{m}$.
By Lemma 3.9 there exist $z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$ so
that $y=E(z\otimes x)$. Then, for any $b\in{\mathbb{F}}$ we have

$\displaystyle\widehat{A}\left(\left(z+be_{j_{0}}\right)\otimes x\right)$
$\displaystyle=E\left(\left(z+be_{j_{0}}\right)\otimes
x\right)+\alpha\left(\vec{\mathbf{1}}_{nq}^{T}-\vec{\mathbf{1}}_{m}^{T}E\right)\left(\left(z+be_{j_{0}}\right)\otimes
x\right)$
$\displaystyle=y+\alpha\left(\vec{\mathbf{1}}_{nq}^{T}\left(\left(z+be_{j_{0}}\right)\otimes
x\right)-\vec{\mathbf{1}}_{m}^{T}y\right)$
$\displaystyle=y+\alpha\mbox{$\left(\left(\sum_{j=1}^{q}z_{j}\right)\left(\sum_{i=1}^{n}x_{i}\right)+b\left(\sum_{i=1}^{n}x_{i}\right)-\left(\sum_{k=1}^{m}y_{k}\right)\right)$}.$

To prove our claim we will show that for every $y$ we can find $x$, $z$ and
$b$ so that the second term becomes 0. Note that this can always be arranged
if we have $y=E(z\otimes x)$ with $\sum_{i=1}^{n}x_{i}\neq 0$. In that case,
simply take

$b=\frac{\sum_{k=1}^{m}y_{k}-\left(\sum_{j=1}^{q}z_{j}\right)\left(\sum_{i=1}^{n}x_{i}\right)}{\left(\sum_{i=1}^{n}x_{i}\right)}.$
(3.18)

First we consider a case where this may not happen, after which we show that
in all remaining cases it is possible to have $\sum_{i=1}^{n}x_{i}\neq 0$.

#### Case 1

Assume that $i_{k}\neq i_{l}$ for all $k\neq l$. In this case $x$ and $z$ with
$y=E(z\otimes x)$ can be obtained by setting $z_{j}=1$ for all $j$,
$x_{i_{k}}=y_{k}$ and $x_{i}=0$ for $i\neq i_{1},\ldots,i_{m}.$ Then
$\sum_{k=1}^{m}y_{k}=\sum_{i=1}^{n}x_{i}$. Then, in case
$\sum_{k=1}^{m}y_{k}\neq 0$, also $\sum_{i=1}^{n}x_{i}\neq 0$ and we can take
$b$ as in (3.18). In case $\sum_{k=1}^{m}y_{k}=0$, we also have
$\sum_{i=1}^{n}x_{i}=0$ and thus

$\left(\sum_{j=1}^{q}z_{j}\right)\left(\sum_{i=1}^{n}x_{i}\right)+b\left(\sum_{i=1}^{n}x_{i}\right)-\left(\sum_{k=1}^{m}y_{k}\right)=0$

irrespectively of the choice of $b$. Hence both for $\sum_{k=1}^{m}y_{k}\neq
0$ and $\sum_{k=1}^{m}y_{k}=0$ we can find $z$ and $x$ with
$y=\widehat{A}(z\otimes x)$.

#### Case 2

Assume that $j_{k}\neq j_{l}$ for all $k\neq l$. In that case take $x_{i}=1$
for all $i$, $z_{j_{k}}=y_{k}$ for all $k$ and $z_{j}=0$ for $j\neq
j_{1},\ldots,j_{m}$. Then $y=E(z\otimes x)$ and $\sum_{i=1}^{n}x_{i}=n\neq 0$
so that we can take $b$ as in (3.18).

#### Case 3

Assume we are neither in Case 1 nor in Case 2. Since (C1) holds this implies
that, after possibly rearranging indices of $L_{1},\ldots,L_{m}$ as well as
block columns and rows in $L$ (see Remark 3.7), there exist $s,r>1$ so that
$i_{k}=k$ and $j_{k}=1$ for $k=1,\ldots,r$, $i_{r+l}=r+1$ and $j_{r+l}=l+1$
for $l=1,\ldots,s$ and $i_{r+s+1}=r+2$, $j_{r+s+1}=s+2$, while $i_{p}\neq
1,\ldots,r+2$ and $j_{p}\neq 1,\ldots,s+2$ for $p>r+s+1$. Let
$y\in{\mathbb{F}}^{m}$ be given as $y=E(z\otimes x)$ for some
$z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$. Then $y_{k}=x_{k}z_{1}$ for
$k=1,\ldots,r$, $y_{r+l}=x_{r+1}z_{1+l}$ for $l=1,\ldots,s$ and
$y_{r+s+1}=x_{r+2}z_{s+2}$, while $z_{1},\ldots,z_{s+2},x_{1},\ldots,x_{r+2}$
do not occur in the factorisations $y_{p}=x_{i_{p}}z_{j_{p}}$ for $p>r+s+1$.
As we did in the proof of Lemma 3.15 for (C2.7), we will adjust $z$ and $x$
while maintaining $y=E(z\otimes x)$ and in this case arranging
$\sum_{i=1}^{n}x_{i}\neq 0$. Redefine $z_{1}:=1$, $x_{i}:=y_{i}$ for
$i=1,\ldots,r$, select $0\neq
x_{r+1}\neq-\sum_{i={r+2}}^{n}x_{i}-\sum_{k=1}^{r}y_{k}$ and redefine
$z_{1+j}:=y_{r+j}/x_{r+1}$ for $j=1,\ldots,s$. In that case we still have
$y_{k}=x_{i_{k}}y_{j_{k}}$ for $k=1,\ldots,s+r+1$ while the other identities
remain unaffected and also

$\sum_{i=1}^{n}x_{i}=\sum_{k=1}^{r}y_{k}+x_{r+1}+\sum_{i=r+2}^{n}x_{i}\neq 0.$

Hence, for these redefined $x$ and $z$ we can take $b$ as in (3.18). ∎

######  Lemma 3.22.

Assume condition (C1) in (3.4) together with (C2.5) or (C2.6) holds. Assume
also that $\sum_{k=1}^{m}\alpha_{k}=1$. Then
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

###### Proof.

We give a proof of the case where (C1) and (C2.6) hold. For (C1) and (C2.5) a
similar argument applies. Hence, assume (C1) and (C2.6) hold. Note that (C2.6)
in fact implies (C1). Also, we have $m\leq q$. However, if $m<q$, then also
(C2.2) holds and we obtain that
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ from Lemma 3.21. Hence we may
assume that $m=q$ and, possibly after relabeling $L_{1},\ldots,L_{m}$ and
rearranging block rows (see Remark 3.7), that $j_{k}=k$ for $k=1,\ldots,m$.
Note that we can write

$\widehat{A}(z\otimes x)=\widehat{A}(I_{q}\otimes x)z.$

Hence, we obtain that ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ in case
we can find a $x\in{\mathbb{F}}^{n}$ so that $\widehat{A}(I_{q}\otimes
x)\in{\mathbb{F}}^{m\times m}$ has full row rank, or, equivalently, is
invertible.

We have $E(I_{q}\otimes
x)=\textup{diag}(x_{i_{1}},\ldots,x_{i_{m}})=E^{T}(I_{q}\otimes x)^{T}$, which
is invertible precisely when $x_{i_{k}}\neq 0$ for all $k$, and

$\displaystyle v^{T}\left(I_{q}\otimes x\right)$
$\displaystyle=\sum_{i=1}^{n}x_{i}\vec{\mathbf{1}}_{q}^{T}-\vec{\mathbf{1}}_{q}^{T}E\left(I_{q}\otimes
x\right).$

Restricting to $x_{i_{k}}\neq 0$ for all $k$ and applying the Sherman–Morrison
formula [3] to

$\widehat{A}\left(I_{q}\otimes x\right)=E\left(I_{q}\otimes x\right)+\alpha
v^{T}\left(I_{q}\otimes x\right)$

it follows that $\widehat{A}(I_{q}\otimes x)$ is invertible if and only if

$\displaystyle-1$ $\displaystyle\neq v^{T}\left(I_{q}\otimes
x\right)\left(E\left(I_{q}\otimes
x\right)\right)^{-1}\alpha=\sum_{i=1}^{n}x_{i}\vec{\mathbf{1}}_{q}^{T}\left(E\left(I_{q}\otimes
x\right)\right)^{-1}\alpha-\vec{\mathbf{1}}_{q}^{T}\alpha$
$\displaystyle=\sum_{i=1}^{n}x_{i}\begin{bmatrix}x_{i_{1}}^{-1}&\cdots&x_{i_{m}}^{-1}\end{bmatrix}\alpha-\sum_{k=1}^{m}\alpha_{k}=\sum_{i=1}^{n}x_{i}\begin{bmatrix}x_{i_{1}}^{-1}&\cdots&x_{i_{m}}^{-1}\end{bmatrix}\alpha-1.$

Thus we need to find an $x\in{\mathbb{F}}^{n}$ with $x_{i_{k}}\neq 0$ for all
$k$ so that

$\sum_{i=1}^{n}x_{i}\begin{bmatrix}x_{i_{1}}^{-1}&\cdots&x_{i_{m}}^{-1}\end{bmatrix}\alpha\neq
0.$

This can simply be done by selecting $x_{i}=1$ for all $i$, giving $n$ on the
left hand side, since by assumption $\sum_{k=1}^{m}\alpha_{k}=1$. Hence we can
choose $x$ so that $\widehat{A}(I_{q}\otimes x)$ is invertible, which implies
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$. ∎

######  Lemma 3.23.

Assume condition (C1) in (3.4) together with (C2.3) or (C2.4) holds. Assume
also that $\sum_{k=1}^{m}\alpha_{k}=1$. Then
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

###### Proof.

We give a proof of the case where (C1) and (C2.4) hold. For (C1) and (C2.3) a
similar argument applies. Hence, assume (C1) and (C2.4) hold. Since the claim
is proved for (C1) together with (C2.5) in Lemma 3.22 we will exclude
condition (C2.5).

As in the proof of Lemma 3.15 we note that there exist $r,s>1$ (but $r+s\leq
n$) so that, possibly after rearranging the indices of $L_{1},\ldots,L_{m}$ as
well as block columns and rows in $L$ (see Remark 3.7), $j_{k}=1$ and
$i_{k}=k$ for $k=1,\ldots,r$ and $j_{r+l}=2$ and $i_{r+l}=r+l$ for
$l=1,\ldots,s$, while $j_{k}\neq 1,2$ and $i_{k}\neq 1,\ldots,r+s$ whenever
$k>r+s$. Furthermore, since (C2.5) is excluded we may assume that there exists
a $p>1$ such that $i_{r+s+i}=i_{r+s+1}$ and $j_{r+s+i}=2+i$ for
$i=1,\ldots,p$, while $j_{k}\neq 1,\ldots,2+p$ and $i_{k}\neq 1,\ldots,r+s+1$
whenever $k>r+s+p$.

Now fix a $y^{\circ}\in{\mathbb{F}}^{m}$. Using Lemma 3.14 and (3.5) it
follows that there exist $y\in{\mathbb{F}}^{m}$ and $\lambda\in{\mathbb{F}}$
so that
$y^{\circ}=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y+\alpha\lambda$
and for this $y$ there exist $z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$
so that $y=E(z\otimes x)$. Then $y_{k}=x_{k}z_{1}$ for $k=1,\ldots,r$ and
$y_{r+k}=x_{r+k}z_{2}$ for $k=1,\ldots,s$ and $y_{r+s+k}=x_{r+s+1}z_{2+k}$ for
$k=1,\ldots,p$, while $z_{1},\ldots,z_{2+p},x_{1},\ldots,x_{r+s+1}$ do not
occur in the factorisations $y_{k}=x_{i_{k}}z_{j_{k}}$ for $k>r+s+p$. We claim
that we can adjust $z$ and $x$ in such a way that still $y=E(z\otimes x)$ and
in addition $\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=\lambda$. Once this is
achieved, we obtain that

$y^{\circ}=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y+\alpha\lambda=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)E(z\otimes
x)+\alpha\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=\widehat{A}(z\otimes x),$

and we may conclude that ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$,
since $y^{\circ}$ was chosen arbitrarily.

To see that $z$ and $x$ can be adjusted in the desired way, we will only
modify $z_{1},z_{2},x_{r+s+1}$, subject to $z_{1},z_{2},x_{r+s+1}\neq 0$, so
that $x_{k}$ for $k=1,\ldots,r+s$ and $z_{k}$ for $k=3,\ldots,2+p$ are fixed
by the above equations while the other values of $x_{i}$ and $z_{j}$ remain
unchanged. This guarantees that $y=E(z\otimes x)$ remains true. Set

$\displaystyle{\widetilde{y}}_{1}:=\sum_{k=1}^{r}y_{k},\quad{\widetilde{y}}_{2}:=\sum_{k=r+1}^{r+s}y_{k},\quad{\widetilde{y}}_{3}:=\sum_{k=r+s+1}^{r+s+p}y_{k},$
$\displaystyle\lambda_{1}:=\sum_{i=r+s+2}^{n}x_{i},\quad\lambda_{2}:=\sum_{j=2+p+1}^{q}z_{j}.$

Then

$\displaystyle\sum_{i=1}^{n}x_{i}$
$\displaystyle=\sum_{i=1}^{r+s}x_{i}+x_{r+s+1}+\sum_{i=r+s+2}^{n}x_{i}=\sum_{i=1}^{r}\frac{y_{i}}{z_{1}}+\sum_{i=r+1}^{r+s}\frac{y_{i}}{z_{2}}+x_{r+s+1}+\lambda_{1}$
$\displaystyle=\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{{\widetilde{y}}_{2}}{z_{2}}+x_{r+s+1}+\lambda_{1},$

and via a similar computation

$\sum_{j=1}^{q}z_{j}=z_{1}+z_{2}+\frac{{\widetilde{y}}_{3}}{x_{r+s+1}}+\lambda_{2}.$

Thus the objective is to find $z_{1},z_{2},x_{r+s+1}\neq 0$ so that

$\left(\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{{\widetilde{y}}_{2}}{z_{2}}+x_{r+s+1}+\lambda_{1}\right)\left(z_{1}+z_{2}+\frac{{\widetilde{y}}_{3}}{x_{r+s+1}}+\lambda_{2}\right)=\lambda.$

In case one of ${\widetilde{y}}_{1},{\widetilde{y}}_{2},{\widetilde{y}}_{3}$
is zero, this ensures that one of the variables only appears in one of the two
factors, after which the objective is easy to achieve. When $\lambda=0$,
$z_{1}$ and $z_{2}$ can be chosen (with $z_{1},z_{2}\neq 0$) so that the
second factor becomes zero, and the identity is satisfied. Thus, assume
$\lambda,{\widetilde{y}}_{1},{\widetilde{y}}_{2},{\widetilde{y}}_{3}\neq 0$.

Now we select $x_{r+s+1}$ so that the first factor becomes equal to 1, i.e.,
$x_{r+s+1}=1-\lambda_{1}-\frac{{\widetilde{y}}_{1}}{z_{1}}-\frac{{\widetilde{y}}_{2}}{z_{2}}$,
and insert this into the second factor so that we arrive at

$\lambda=z_{1}+z_{2}+\frac{{\widetilde{y}}_{3}}{x_{r+s+1}}+\lambda_{2}=z_{1}+z_{2}+\frac{{\widetilde{y}}_{3}z_{1}z_{2}}{(1-\lambda_{1})z_{1}z_{2}-{\widetilde{y}}_{1}z_{2}-{\widetilde{y}}_{2}z_{1}}+\lambda_{2},$

keeping in mind the conditions $z_{1},z_{2}\neq 0$,
$\lambda_{1}+\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{{\widetilde{y}}_{2}}{z_{2}}\neq
1$. Multiplying with
$(1-\lambda_{1})z_{1}z_{2}-{\widetilde{y}}_{1}z_{2}-{\widetilde{y}}_{2}z_{1}$
on both sides this leads to a second order polynomial equation in $z_{1}$ with
parameters depending on $z_{2}$:

$a(z_{2})z_{1}^{2}+b(z_{2})z_{1}+c(z_{2})=0$

with

$\displaystyle a(z_{2})=z_{2}\left(1-\lambda_{1}\right)$
$\displaystyle-{\widetilde{y}}_{2},\quad
c(z_{2})=z_{2}\left(\lambda-\lambda_{2}\right){\widetilde{y}}_{1}-z_{2}^{2}{\widetilde{y}}_{1},$
$\displaystyle b(z_{2})=z_{2}^{2}\left(1-\lambda_{1}\right)+z_{2}$
$\displaystyle\left({\widetilde{y}}_{3}-{\widetilde{y}}_{1}-{\widetilde{y}}_{2}-\left(1-\lambda_{1}\right)\left(\lambda-\lambda_{2}\right)\right)+{\widetilde{y}}_{2}\left(\lambda-\lambda_{2}\right).$

First assume $\lambda_{1}\neq 1$. In that case $b(z_{2})^{2}$ is a polynomial
in $z_{2}$ of order 4 while $4a(z_{2})c(z_{2})$ is of order 3. Hence, taking
$z_{2}$ large enough, avoiding $\frac{{\widetilde{y}}_{2}}{1-\lambda_{1}}$ and
$\lambda-\lambda_{2}$ so that $a(z_{2})$ and $c(z_{2})$ are non-zero, we end
up with two non-zero solutions for $z_{1}$, which are real in case
${\mathbb{F}}={\mathbb{R}}$, so that for at least one of the solutions for
$z_{1}$ we will have
$\lambda_{1}+\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{{\widetilde{y}}_{2}}{z_{2}}\neq
1$.

Now assume $\lambda_{1}=1$. Then $c\left(z_{2}\right)$ is unchanged and

$\displaystyle a\left(z_{2}\right)=-{\widetilde{y}}_{2},\quad
b\left(z_{2}\right)=z_{2}\left({\widetilde{y}}_{3}-{\widetilde{y}}_{1}-{\widetilde{y}}_{2}\right)+{\widetilde{y}}_{2}\left(\lambda-\lambda_{2}\right).$

In this case $b\left(z_{2}\right)^{2}-4a\left(z_{2}\right)c\left(z_{2}\right)$
is a polynomial of degree at most two with constant term
${\widetilde{y}}_{2}^{2}\left(\lambda-\lambda_{2}\right)^{2}$. If
$\lambda\neq\lambda_{2}$, this constant term is positive and taking $z_{2}\neq
0$ small enough, avoiding $\lambda-\lambda_{2}$ so that again
$a\left(z_{2}\right)$ and $c\left(z_{2}\right)$ are non-zero, we again arrive
at two non-zero solutions for $z_{1}$ (being real in case
${\mathbb{F}}={\mathbb{R}}$) so that for one of them we have
$\lambda_{1}+\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{{\widetilde{y}}_{2}}{z_{2}}\neq
1$.

Finally, we consider the case where $\lambda_{1}=1$ and $\lambda_{2}=\lambda$.
This means, since both $\lambda_{1},\lambda_{2}\neq 0$, that $m>r+s+p$ and
that $q>p+2$ and $n>r+s+1.$ We show that in this case $x$ and $z$ can be
modified in such a way that $y^{\circ}=\widehat{A}(z\otimes x)$ remains true
while also $\lambda_{1}\neq 1$ or $\lambda_{2}\neq\lambda$ holds, so that the
constructions of the previous paragraphs can be applied.

By rearranging some of the indices of $L_{r+p+s},\ldots,L_{m}$ and reordering
some of the block rows and columns (see Remark 3.7) we can arrange to have
$y_{m}=x_{n}z_{q}$ as the last equation in $y=E(z\otimes x)$. Since (C1)
holds, we know either $z_{q}$ or $x_{n}$ occurs only in a single factorisation
$y_{k}=x_{i_{k}}z_{j_{k}}$ (hence with $k=m$). Assume $x_{n}$ occurs only in
$y_{m}=x_{n}z_{q}$. Take $a\in{\mathbb{F}}$ so that $a\neq 0$ and $a\neq-
z_{q}$. Adjust $z_{q}$ to $z_{q}+a$ and redefine
$x_{i_{k}}:=\frac{y_{k}}{z_{q}+a}$ whenever $j_{k}=q$. Note that $x_{j_{k}}$
cannot occur in another factorisation $y_{k}=x_{i_{k}}z_{j_{k}}$ when
$j_{k}=q$, since either $k=m$ (so that $i_{k}=n$) or since there is more than
one $k$ with $j_{k}=q$ and (C1) is in place. Hence, with these modifications
$y=E(z\otimes x)$ still holds while $\lambda_{2}$ is adjusted to
$\lambda_{2}+a\neq\lambda$. A similar argument allows one to adjust $x$ and
$z$ to achieve $\lambda_{1}\neq 1$ in case $z_{q}$ occurs only in the
factorisation $y_{m}=x_{n}z_{q}$. ∎

######  Lemma 3.24.

Assume condition (C1) in (3.4) together with (C2.7) holds. Assume also that
$\sum_{k=1}^{m}\alpha_{k}=1$. Then
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

###### Proof.

Since all other cases are covered, we may assume the conditions (C2.1) to
(C2.6) do not hold. By excluding the case $m=1$, reasoning as for (C2.4) again
after possibly rearranging the indices of $L_{1},\ldots,L_{m}$ as well as
block columns and rows in $L$ (see Remark 3.7), it follows that there exist
$r,s>1$ (with $r+s+1\leq m$) so that $i_{k}=k$ and $j_{k}=1$ for
$k=1,\ldots,r$, $i_{r+l}=r+1$ and $j_{r+l}=l+1$ for $l=1,\ldots,s$ and
$i_{r+s+1}=r+2$, $j_{r+s+1}=s+2$, while $i_{p}\neq 1,\ldots,r+2$ and
$j_{p}\neq 1,\ldots,s+2$ for $p>r+s+1$. Now fix a
$y^{\circ}\in{\mathbb{F}}^{m}$. Using Lemma 3.14 and (3.5) it follows that
there exist $y\in{\mathbb{F}}^{m}$ and $\lambda\in{\mathbb{F}}$ so that
$y^{\circ}=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y+\alpha\lambda$
and for this $y$ there exist $z\in{\mathbb{F}}^{q}$ and $x\in{\mathbb{F}}^{n}$
so that $y=E(z\otimes x)$. Then $y_{k}=x_{k}z_{1}$ for $k=1,\ldots,r$,
$y_{r+l}=x_{r+1}z_{1+l}$ for $l=1,\ldots,s$ and $y_{r+s+1}=x_{r+2}z_{s+2}$,
while $z_{1},\ldots,z_{s+2},x_{1},\ldots,x_{r+2}$ do not occur in the
factorisations $y_{p}=x_{i_{p}}z_{j_{p}}$ for $p>r+s+1$. We claim that we can
adjust $z$ and $x$ in such a way that still $y=E(z\otimes x)$ and in addition
$\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=\lambda$. Once this is achieved, we
obtain that

$y^{\circ}=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y+\alpha\lambda=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)E(z\otimes
x)+\alpha\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=\widehat{A}(z\otimes x),$

and we may conclude that ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$,
since $y^{\circ}$ was chosen arbitrarily.

To see that $z$ and $x$ can be adjusted in the desired way, we will only
modify $z_{1},x_{r+1}$ and one of $x_{r+2}$ or $z_{s+2}$, subject to
$z_{1},x_{r+1},x_{r+2},z_{s+2}\neq 0$, so that $x_{k}$ for $k=1,\ldots,r$,
$z_{k}$ for $k=2,\ldots,s+1$ and either $x_{r+2}$ or $z_{s+2}$ are fixed by
the above equations while the other values of $x_{i}$ and $z_{j}$ remain
unchanged. This guarantees that $y=E(z\otimes x)$ remains true. Set

$\displaystyle{\widetilde{y}}_{1}:=\sum_{k=1}^{r}y_{k},\quad{\widetilde{y}}_{2}:=\sum_{k=r+1}^{r+s}y_{k},\quad\lambda_{1}:=\sum_{i=r+3}^{n}x_{i},\quad\lambda_{2}:=\sum_{j=s+3}^{q}z_{j}.$

Then

$\displaystyle\sum_{i=1}^{n}x_{i}$
$\displaystyle=\sum_{i=1}^{r}x_{i}+x_{r+1}+x_{r+2}+\sum_{i=r+3}^{n}x_{i}=\sum_{i=1}^{r}\frac{y_{i}}{z_{1}}+x_{r+1}+\frac{y_{r+s+1}}{z_{s+2}}+\lambda_{1}$
$\displaystyle=\frac{{\widetilde{y}}_{1}}{z_{1}}+x_{r+1}+\frac{y_{r+s+1}}{z_{s+2}}+\lambda_{1},$

and via a similar computation

$\sum_{j=1}^{q}z_{j}=z_{1}+z_{s+2}+\frac{{\widetilde{y}}_{2}}{x_{r+1}}+\lambda_{2}.$

Thus the objective is to find $z_{1},x_{r+1},z_{s+2}\neq 0$ so that

$\left(\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{y_{r+s+1}}{z_{s+2}}+x_{r+1}+\lambda_{1}\right)\left(z_{1}+z_{s+2}+\frac{{\widetilde{y}}_{2}}{x_{r+1}}+\lambda_{2}\right)=\lambda.$

In case one of ${\widetilde{y}}_{1},{\widetilde{y}}_{2},y_{r+s+1}$ is zero,
this ensures that one of the variables only appears in one of the two factors,
after which the objective is easy to achieve. When $\lambda=0$, $z_{1}$ and
$z_{s+2}$ can be chosen (with $z_{1},z_{s+2}\neq 0$) so that the second factor
becomes zero, and the identity is satisfied. Thus, assume
$\lambda,{\widetilde{y}}_{1},{\widetilde{y}}_{2},y_{r+s+1}\neq 0$.

Now we select $x_{r+1}$ so that the first factor becomes equal to 1, i.e.,
$x_{r+1}=1-\lambda_{1}-\frac{{\widetilde{y}}_{1}}{z_{1}}-\frac{y_{r+s+1}}{z_{s+2}}$,
and insert this into the second factor so that we arrive at

$\lambda=z_{1}+z_{s+2}+\frac{{\widetilde{y}}_{2}}{x_{r+1}}+\lambda_{2}=z_{1}+z_{s+2}+\frac{{\widetilde{y}}_{2}z_{1}z_{s+2}}{(1-\lambda_{1})z_{1}z_{s+2}-{\widetilde{y}}_{1}z_{s+2}-y_{r+s+1}z_{1}}+\lambda_{2},$

keeping in mind the conditions $z_{1},z_{s+2}\neq 0$,
$\lambda_{1}+\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{y_{r+s+1}}{z_{s+2}}\neq
1$. Multiplying with
$(1-\lambda_{1})z_{1}z_{s+2}-{\widetilde{y}}_{1}z_{s+2}-y_{r+s+1}z_{1}$ on
both sides this leads to a second order polynomial equation in $z_{1}$ with
parameters depending on $z_{s+2}$:

$a\left(z_{s+2}\right)z_{1}^{2}+b\left(z_{s+2}\right)z_{1}+c\left(z_{s+2}\right)=0$

with

$\displaystyle a\left(z_{s+2}\right)$
$\displaystyle=z_{s+2}\left(1-\lambda_{1}\right)-y_{r+s+1},\quad
c\left(z_{s+2}\right)=z_{s+2}\left(\lambda-\lambda_{2}\right){\widetilde{y}}_{1}-z_{s+2}^{2}{\widetilde{y}}_{1},$
$\displaystyle b\left(z_{s+2}\right)$
$\displaystyle=z_{s+2}^{2}\left(1-\lambda_{1}\right)+z_{s+2}\left({\widetilde{y}}_{2}-{\widetilde{y}}_{1}-y_{r+s+1}-\left(1-\lambda_{1}\right)\left(\lambda-\lambda_{2}\right)\right)+$
$\displaystyle\qquad\qquad\qquad+y_{r+s+1}\left(\lambda-\lambda_{2}\right).$

First assume $\lambda_{1}\neq 1$. In that case $b\left(z_{s+2}\right)^{2}$ is
a polynomial in $z_{s+2}$ of order 4 while
$4a\left(z_{s+2}\right)c\left(z_{s+2}\right)$ is of order 3. Hence, taking
$z_{s+2}$ large enough, avoiding $\frac{y_{r+s+1}}{1-\lambda_{1}}$ and
$\frac{{\widetilde{y}}_{1}(\lambda-\lambda_{2})}{{\widetilde{y}}_{1}}$ so that
$a\left(z_{s+2}\right)$ and $c\left(z_{s+2}\right)$ are non-zero, we end up
with two non-zero solutions for $z_{1}$, which are real in case
${\mathbb{F}}={\mathbb{R}}$, so that at least one of the solutions for $z_{1}$
will satisfy
$\lambda_{1}+\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{y_{r+s+1}}{z_{s+2}}\neq
1$.

Now assume $\lambda_{1}=1$. Then $c\left(z_{s+2}\right)$ is unchanged and

$\displaystyle a\left(z_{s+2}\right)=-y_{r+s+1},\quad
b\left(z_{s+2}\right)=z_{s+2}\left({\widetilde{y}}_{2}-{\widetilde{y}}_{1}-y_{r+s+1}\right)+y_{r+s+1}\left(\lambda-\lambda_{2}\right).$

In this case
$b\left(z_{s+2}\right)^{2}-4a\left(z_{s+2}\right)c\left(z_{s+2}\right)$ is a
polynomial of degree at most two with constant term
$y_{r+s+1}^{2}\left(\lambda-\lambda_{2}\right)^{2}$. If
$\lambda\neq\lambda_{2}$, this constant term is positive and taking
$z_{s+2}\neq 0$ small enough, avoiding $\lambda-\lambda_{2}$ so that again
$a\left(z_{s+2}\right)$ and $c\left(z_{s+2}\right)$ are non-zero, we again
arrive at two non-zero solutions for $z_{1}$ (being real in case
${\mathbb{F}}={\mathbb{R}}$) so that one of them satisfies
$\lambda_{1}+\frac{{\widetilde{y}}_{1}}{z_{1}}+\frac{y_{r+s+1}}{z_{s+2}}\neq
1$.

The case that remains is when $\lambda_{1}=1$ and $\lambda_{2}=\lambda$, which
implies that $m>r+s+1$, $q>s+2$ and $n>r+2$, since
$\lambda_{1},\lambda_{2}\neq 0$. By a similar argument as used in the last
paragraph of the proof of Lemma 3.23 the vectors $x$ and $z$ can be modified
to obtain $\lambda_{1}\neq 1$ or $\lambda_{2}\neq\lambda$, so that the
constructions of the previous paragraphs can be applied. ∎

Lastly we prove for case (iii) in Lemma 3.15 that
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ when
$\sum_{k=1}^{m}\alpha_{k}=1$.

######  Lemma 3.25.

Assume $L$ is as in case (iii) of Lemma 3.15 and $\sum_{k=1}^{m}\alpha_{k}=1$.
Then ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$.

###### Proof.

Assume $L$ has the form as in case (iii) in Lemma 3.15 and
$\sum_{k=1}^{m}\alpha_{k}=1$. Fix a $y\in{\mathbb{F}}^{m}$. Using Lemma 3.14
it follows that there exist $y^{\circ}\in{\mathbb{F}}^{m}$ and
$\lambda\in{\mathbb{F}}$ so that
$y=\left(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}\right)y^{\circ}+\alpha\lambda$.
Then by Lemma 3.18 for all $x_{r},z_{s}\neq 0$ there exist unique vectors $x$
and $z$, with $x_{r}$ and $z_{s}$ in the indicated positions of $x$ and $z$,
respectively, so that $y^{\circ}=E(z\otimes x)$ and with
$\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)$ as in (3.12). In the remainder of the
proof we show that $x_{r}$ and $z_{s}$ can be chosen in such a way that
$\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=\lambda$. Once that is established, it
follows that

$y=(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T})y^{\circ}+\alpha\lambda=(I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T})E(z\otimes
x)+\alpha\vec{\mathbf{1}}_{nq}^{T}(z\otimes x)=\widehat{A}(z\otimes x),$

and the proof is complete because $y\in{\mathbb{F}}^{m}$ was chosen
arbitrarily.

Since $\sum_{k=1}^{m}\alpha_{k}=1$, we have
$\textup{Ker\,}I_{m}-\alpha\vec{\mathbf{1}}_{m}^{T}=\operatorname{span}\\{\alpha\\}$,
by Lemma 3.14. This implies that $y^{\circ}$ can be written as
$y^{\circ}=y^{\prime}+\rho\alpha$ with $y^{\prime}\perp\alpha$ and
$\rho\in{\mathbb{F}}$ is another variable we can select arbitrarily. Set

$\displaystyle{\widetilde{y}}^{\prime}_{1}:=\sum_{k=1}^{q-1}y^{\prime}_{k},\quad{\widetilde{y}}^{\prime}_{2}:=\sum_{k=q}^{m}y^{\prime}_{k},\quad\widetilde{\alpha}_{1}:=\sum_{k=1}^{q-1}\alpha_{k},\quad\widetilde{\alpha}_{2}:=\sum_{k=q}^{m}\alpha_{k},$

so that

${\widetilde{y}}_{1}^{\circ}:=\sum_{k=1}^{q-1}y^{\circ}_{k}={\widetilde{y}}^{\prime}_{1}+\rho{\widetilde{\alpha}}_{1}\quad\mbox{and}\quad{\widetilde{y}}_{2}^{\circ}:=\sum_{k=q}^{m}y^{\circ}_{k}={\widetilde{y}}^{\prime}_{2}+\rho{\widetilde{\alpha}}_{2}.$

Hence, using (3.12) and the above formulas for ${\widetilde{y}}_{1}^{\circ}$
and ${\widetilde{y}}_{2}^{\circ}$ the equation to solve becomes

$\left(\frac{{\widetilde{y}}^{\prime}_{2}+\rho{\widetilde{\alpha}}_{2}}{z_{s}}+x_{r}\right)\left(\frac{{\widetilde{y}}^{\prime}_{1}+\rho{\widetilde{\alpha}}_{1}}{x_{r}}+z_{s}\right)=\lambda$
(3.19)

with variables $x_{r},z_{s},\rho\in{\mathbb{F}}$ subject to $x_{r},z_{s}\neq
0$. We show this equation can be solved by considering three cases.

#### Case 1

Assume $\lambda=0$. Take $z_{s}=x_{r}=1$ and
$\rho=\frac{-\left({\widetilde{y}}^{\prime}_{2}+1\right)}{{\widetilde{\alpha}}_{2}}$.

#### Case 2

Assume
${\widetilde{y}}^{\prime}_{1}\neq\lambda+\frac{{\widetilde{\alpha}}_{1}{\widetilde{y}}^{\prime}_{2}}{{\widetilde{\alpha}}_{2}}$.
Take $\rho=\frac{-{\widetilde{y}}^{\prime}_{2}}{{\widetilde{\alpha}}_{2}}$.
Then

${\widetilde{y}}^{\prime}_{2}+\rho{\widetilde{\alpha}}_{2}=0\quad\mbox{and}\quad{\widetilde{y}}^{\prime}_{1}+\rho{\widetilde{\alpha}}_{1}={\widetilde{y}}^{\prime}_{1}-\frac{{\widetilde{\alpha}}_{1}{\widetilde{y}}^{\prime}_{2}}{{\widetilde{\alpha}}_{2}}\neq\lambda.$

Thus (3.19) holds with $x_{r}=1$ and
$z_{s}=\lambda-\left({\widetilde{y}}^{\prime}_{1}-\frac{{\widetilde{\alpha}}_{1}{\widetilde{y}}^{\prime}_{2}}{{\widetilde{\alpha}}_{2}}\right)\neq
0$.

#### Case 3

Assume $\lambda\neq 0$ and
${\widetilde{y}}^{\prime}_{1}=\lambda+\frac{{\widetilde{\alpha}}_{1}{\widetilde{y}}^{\prime}_{2}}{{\widetilde{\alpha}}_{2}}$.
Write $\rho$ as
$\rho=\frac{\beta-{\widetilde{y}}^{\prime}_{2}}{{\widetilde{\alpha}}_{2}}$
with $\beta\in{\mathbb{F}}$ arbitrary. In this case (3.19) turns into

$\left(\frac{\beta}{z_{s}}+x_{r}\right)\left(\frac{\lambda+\beta\frac{{\widetilde{\alpha}}_{1}}{{\widetilde{\alpha}}_{2}}}{x_{r}}+z_{s}\right)=\lambda.$

Set $z_{s}=1$ and multiply both sides with $x_{r}$. This yields the equation

$0=\left(\beta+x_{r}\right)\left(\mbox{$\lambda+\beta\frac{{\widetilde{\alpha}}_{1}}{{\widetilde{\alpha}}_{2}}$}+x_{r}\right)-\lambda
x_{r}=x_{r}^{2}+\beta\left(1+\mbox{$\frac{{\widetilde{\alpha}}_{1}}{{\widetilde{\alpha}}_{2}}$}\right)x_{r}+\beta\left(\mbox{$\lambda+\beta\frac{{\widetilde{\alpha}}_{1}}{{\widetilde{\alpha}}_{2}}$}\right).$

In case ${\widetilde{\alpha}}_{1}={\widetilde{\alpha}}_{2}$, take $\beta$ so
that $\beta(\lambda+\beta)\neq 0$ (with $\beta(\lambda+\beta)<0$ if
${\mathbb{F}}={\mathbb{R}}$) to obtain a non-zero solution for $x_{r}$ (which
is real in case if ${\mathbb{F}}={\mathbb{R}}$).

In case ${\widetilde{\alpha}}_{1}\neq{\widetilde{\alpha}}_{2}$, for
${\mathbb{F}}={\mathbb{C}}$ it is easy to select a $\beta$ so that the
equation has a non-zero solution, while for ${\mathbb{F}}={\mathbb{R}}$ we
need to choose $\beta$ so that

$\beta^{2}\left(1+\mbox{$\frac{{\widetilde{\alpha}}_{1}}{{\widetilde{\alpha}}_{2}}$}\right)^{2}-4\beta\left(\mbox{$\lambda+\beta\frac{{\widetilde{\alpha}}_{1}}{{\widetilde{\alpha}}_{2}}$}\right)=\beta^{2}\left(1-\mbox{$\frac{{\widetilde{\alpha}}_{1}}{{\widetilde{\alpha}}_{2}}$}\right)^{2}-4\beta\lambda>0.$

This can easily be done by taking $\beta$ large enough. ∎

###  3.6. Proof of Theorem 1.1

In this section we merge the results from the previous sections to prove
Theorem 1.1. Throughout we assume condition (C1) in (1.6) holds. Then by Lemma
3.15 either one of the conditions (C2.1)–(C2.7) hold or $L$ is of the form in
(i), (ii) or (iii) listed in the same lemma. Hence, by Corollary 3.2 it
suffices to prove that ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ while
(C1) holds together with each of (C2.1)–(C2.7), (i), (ii) and (iii).

For (i) and (ii) this is a consequence of Lemma 3.17.

Since the matrix $L_{0}$ is in the span of $L_{1},\ldots,L_{m}$ we can write
$L_{0}=\sum_{k=1}^{m}\alpha_{k}L_{k}$.

Assuming $\sum_{k=1}^{m}\alpha_{k}\neq 1$, it is shown that
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ when one of (C2.1)–(C2.7)
holds in Lemma 3.16, while for $L$ as in (iii) it is shown that
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ in Lemma 3.19 for
${\mathbb{F}}={\mathbb{C}}$. For case (iii) with ${\mathbb{F}}={\mathbb{R}}$,
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ need not hold, but nonetheless
positivity and complete positivity still coincide by Lemma 3.20.

Assuming $\sum_{k=1}^{m}\alpha_{k}=1$, it is proved that
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ when (C2.1) or (C2.2) holds in
Lemma 3.21, when (C2.5) or (C2.6) holds in Lemma 3.22, when (C2.3) or (C2.4)
holds in Lemma 3.23, when (C2.7) holds in Lemma 3.24 and when $L$ is as in
(iii) in Lemma 3.25.

Together, these results prove all possible cases, by Lemma 3.15, so that we
obtain that ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ holds whenever
condition (C1) in (1.6) is satisfied, except for the case that is covered in
Lemma 3.20.

###  3.7. All independents $L_{1},\ldots,L_{m}$ in one row or column

In Theorem 1.1 it is required that all matrices other than those selected as
$L_{1},\ldots,L_{m}$ are equal to a single matrix $L_{0}$. Whether this
condition can be removed in general remains unclear. However, in the case that
$L_{1},\ldots,L_{m}$ are all contained in a single block row or block column,
this condition can be removed.

######  Proposition 3.26.

Let ${\mathcal{L}}$ as in (2.1) be a $*$-linear matrix map with matricization
$L$ and Choi matrix ${\mathbb{L}}$. Set $m=\textup{rank\,}{\mathbb{L}}$.
Assume one can choose linearly independent
$L_{1},\ldots,L_{m}\in{\mathbb{F}}^{n\times q}$ among the block entries of
$L$, say $L_{k}=L_{i_{k}j_{k}}$ for $k=1,\ldots m$, in such a way that
$i_{k}=i_{l}$ for all $k$ and $l$ or such that $j_{k}=j_{l}$ for all $k$ and
$l$. In that case ${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$ and hence
${\mathcal{L}}$ is completely positive in case ${\mathcal{L}}$ is positive.

###### Proof.

Assume $i_{1}=\cdots=i_{m}=r\in{1,\ldots,n}$. Then $j_{k}\neq j_{l}$ for
$k\neq l$ and $m\leq q$. Moreover, in $\widehat{A}$ the $(j_{k}-1)n+r$-th
column corresponds to the $k$-th unit vector $e_{k}$ in ${\mathbb{F}}^{m}$.
Let $y\in{\mathbb{F}}^{m}$. Then take $x=e_{r}$ and $z\in{\mathbb{F}}^{q}$
with $z_{i_{k}}=y_{k}$ for $k=1,\ldots,m$ and all other entries of $z$ equal
to 0. It then follows that $\widehat{A}(z\otimes x)=y$. Hence
${\mathfrak{Y}}_{\widehat{A}}={\mathbb{F}}^{m}$, as claimed. A similar
argument applies when $j_{k}=j_{l}$ for all $k$ and $l$. ∎

As a special case of the above result one can consider the case where $L$ is
an analytic or anti-analytic block Toeplitz matrix.

######  Example 3.27.

Consider the case where the $*$-linear map ${\mathbb{L}}$ has an anti-analytic
block Toeplitz matrix structure:

$L=\begin{bmatrix}L_{1}&L_{2}&\cdots&L_{n}\\\ 0&L_{1}&\cdots&L_{n-1}\\\
\vdots&\ddots&\ddots&\vdots\\\ 0&\cdots&0&L_{1}\end{bmatrix}.$

In this case one can take as independent matrices $L_{1},\dots,L_{n}$ (leaving
out some if there is a linear dependency) which are all in the first block
row, so that Proposition 3.26 applies and positivity and complete positivity
coincide.

##  4\. The $2\times 2$ case

In this section we consider all possible cases that can occur when $n=q=2.$
Then $m$ can take values $1,2,3$ and $4$.

#### m=1

Here $L$ can only take the form $L=\left[\begin{smallmatrix}L_{1}&L_{1}\\\
L_{1}&L_{1}\end{smallmatrix}\right]$ with
$L_{1}=\left[\begin{smallmatrix}\ell_{11}&\ell_{11}\\\
\ell_{11}&\ell_{11}\end{smallmatrix}\right]$. Clearly (C1) in (3.4) is met as
well as conditions (C2.1) and (C2.2) of Lemma 3.15, and hence positivity and
complete positivity of ${\mathcal{L}}$ coincide by Lemmas 3.16 and 3.21 and
Corollary 3.2.

#### m=2

In this case, in addition to the selected $L_{1}$ and $L_{2}$ there are two
entries left, say $L_{0}$ and $L_{0}^{\prime}$, that need not be the same. The
four cases for $L$ of the form

$\begin{bmatrix}L_{1}&L_{2}\\\
L_{0}&L_{0}^{\prime}\end{bmatrix},\quad\begin{bmatrix}L_{0}&L_{0}^{\prime}\\\
L_{1}&L_{2}\end{bmatrix},\quad\begin{bmatrix}L_{1}&L_{0}\\\
L_{2}&L_{0}^{\prime}\end{bmatrix},\quad\begin{bmatrix}L_{0}&L_{1}\\\
L_{0}^{\prime}&L_{2}\end{bmatrix},$ (4.1)

are all covered by Proposition 3.26, which does not have the restriction that
$L_{0}$ and $L_{0}^{\prime}$ should be the same. The remaining cases

$\begin{bmatrix}L_{1}&L_{0}\\\
L_{0}^{\prime}&L_{2}\end{bmatrix}\quad\mbox{and}\quad\begin{bmatrix}L_{0}&L_{1}\\\
L_{2}&L_{0}^{\prime}\end{bmatrix}$

are covered by Theorem 1.1 in case $L_{0}=L_{0}^{\prime}$. For $L_{0}\neq
L_{0}^{\prime}$, since $L_{1}$ and $L_{2}$ are linearly independent either
$L_{0}=0$, $L_{1}$ and $L_{0}$ are linearly independent or $L_{2}$ and $L_{0}$
are linearly independent. In the latter two cases we can make a different
selection so that we are in one of the cases in (4.1). Hence, we only need to
consider the case $L_{0}=0$. By a similar argument we can restrict to
$L_{0}^{\prime}=0$, but then $L_{0}=L_{0}^{\prime}$ which is covered by
Theorem 1.1. Hence, in all cases with $m=2$ positivity and complete positivity
of ${\mathcal{L}}$ coincide.

#### m=3

Here we have four cases for $L$:

$\begin{bmatrix}L_{1}&L_{2}\\\
L_{3}&L_{0}\end{bmatrix},\quad\begin{bmatrix}L_{1}&L_{2}\\\
L_{0}&L_{3}\end{bmatrix},\quad\begin{bmatrix}L_{1}&L_{0}\\\
L_{2}&L_{3}\end{bmatrix},\quad\begin{bmatrix}L_{0}&L_{1}\\\
L_{2}&L_{3}\end{bmatrix},$

with only a single matrix that is dependent on the other entries. In neither
of these cases (C1) holds. Keeping Remark 3.7 in mind, we may reorder block
rows and block columns in $L$, so that one only has to deal with one of these
four cases. The case where $L_{0}=0$ is covered in Example 3.10, and in that
case we obtain that positivity and complete positivity of ${\mathcal{L}}$
coincide. However, for the case where $L_{0}\neq 0$, there exists a case,
given by the example below, that proves we can find a positive map
${\mathcal{L}}$ that is not completely positive, at least for
${\mathbb{F}}={\mathbb{R}}$. Hence in that case, it is not automatically true
that positivity and complete positivity coincide. For
${\mathbb{F}}={\mathbb{C}}$, however, we do not know at this stage whether
positivity and complete positivity coincide for $m=3$.

######  Example 4.1.

Consider the case where we have a $*$-linear map ${\mathcal{L}}$ whose
matricization $L\in{\mathbb{F}}^{4\times 4}$ is a $2\times 2$ block Toeplitz
operator

$L=\begin{bmatrix}L_{1}&L_{2}\\\
L_{3}&L_{1}\end{bmatrix}=\begin{bmatrix}a_{1}&b_{1}&a_{2}&b_{2}\\\
c_{1}&a_{1}&c_{2}&a_{2}\\\ a_{3}&b_{3}&a_{1}&b_{1}\\\
c_{3}&a_{3}&c_{1}&a_{1}\end{bmatrix}.$

Since ${\mathcal{L}}$ is $*$-linear, the Choi matrix ${\mathbb{L}}$ is
selfadjoint, and given by

${\mathbb{L}}=\begin{bmatrix}a_{1}&a_{3}&a_{2}&a_{1}\\\
c_{1}&c_{3}&c_{2}&c_{1}\\\ b_{1}&b_{3}&b_{2}&b_{1}\\\
a_{1}&a_{3}&a_{2}&a_{1}\end{bmatrix}=\begin{bmatrix}a_{1}&{\overline{c}}_{1}&{\overline{b}}_{1}&{\overline{a}}_{1}\\\
c_{1}&c_{3}&{\overline{b}}_{3}&{\overline{a}}_{3}\\\
b_{1}&b_{3}&b_{2}&{\overline{a}}_{2}\\\ a_{1}&a_{3}&a_{2}&a_{1}\end{bmatrix}.$

Hence, $*$-linearity of ${\mathcal{L}}$ is equivalent to the Toeplitz
structure in the blocks of $L$ together with
$a_{1},b_{2},c_{3}\in{\mathbb{R}}$, $a_{3}={\overline{c}}_{1}$,
$a_{2}={\overline{b}}_{1}$ and $c_{2}={\overline{b}}_{3}$. Hence,
$*$-linearity of ${\mathcal{L}}$ corresponds to

$L=\begin{bmatrix}a_{1}&b_{1}&{\overline{b}}_{1}&b_{2}\\\
c_{1}&a_{1}&{\overline{b}}_{3}&{\overline{b}}_{1}\\\
{\overline{c}}_{1}&{\overline{c}}_{2}&a_{1}&b_{1}\\\
c_{3}&{\overline{c}}_{1}&c_{1}&a_{1}\end{bmatrix}\quad\mbox{and}\quad{\mathbb{L}}=\begin{bmatrix}a_{1}&{\overline{c}}_{1}&{\overline{b}}_{1}&a_{1}\\\
c_{1}&c_{3}&c_{2}&c_{1}\\\ b_{1}&{\overline{c}}_{2}&b_{2}&b_{1}\\\
a_{1}&{\overline{c}}_{1}&{\overline{b}}_{1}&a_{1}\end{bmatrix}$

with $a_{1},b_{2},c_{3}\in{\mathbb{R}}$ and all others arbitrarily from
${\mathbb{F}}$. In this case

${\mathbb{H}}=\begin{bmatrix}a_{1}&{\overline{b}}_{1}&{\overline{c}}_{1}\\\
b_{1}&b_{2}&{\overline{c}}_{2}\\\
c_{1}&c_{2}&c_{3}\end{bmatrix},\qquad\widehat{A}=\begin{bmatrix}1&0&0&1\\\
0&0&1&0\\\ 0&1&0&0\end{bmatrix}$

and
$\begin{bmatrix}0&1&1\end{bmatrix}^{T}\not\in{\mathfrak{Y}}_{\widehat{A}}$, so
that ${\mathfrak{Y}}_{\widehat{A}}\neq{\mathbb{F}}^{3}$. Indeed, note that

$\widehat{A}(z\otimes x)=\begin{bmatrix}z_{1}x_{1}+z_{2}x_{2}\\\ z_{2}x_{1}\\\
z_{1}x_{2}\end{bmatrix},$

so that if $\begin{bmatrix}a&1&1\end{bmatrix}^{T}=\widehat{A}(z\otimes x)$,
then $z_{2},\,x_{1}$ must be non-zero and of the same sign and $z_{1},\,x_{2}$
must be non-zero and of the same sign, so that $z_{1}x_{1},\,z_{2}x_{2}$ will
be non-zero and of the same sign, and thus $a=z_{1}x_{1}+z_{2}x_{2}$ cannot be
0.

We claim that in this case it can happen that ${\mathcal{L}}$ is positive but
not completely positive, at least for ${\mathbb{F}}={\mathbb{R}}$. Consider
the case where $b_{1}=c_{1}=c_{3}=0$, $a_{1},b_{2}>0$ and $c_{2}=-2a_{1}$.
Then

${\mathbb{H}}=\begin{bmatrix}a_{1}&0&0\\\ 0&b_{2}&-2a_{1}\\\
0&-2a_{1}&0\end{bmatrix}\not\geq 0,$

so that ${\mathcal{L}}$ is not completely positive. Furthermore, we have

$\left(I_{2}\otimes x\right)^{*}{\mathbb{L}}\left(I_{2}\otimes
x\right)=\begin{bmatrix}a_{1}|x_{1}|^{2}&a_{1}x_{2}{\overline{x}}_{1}-2a_{1}x_{1}{\overline{x}}_{2}\\\
a_{1}x_{1}{\overline{x}}_{2}-2a_{1}x_{2}{\overline{x}}_{1}&b_{2}|x_{1}|^{2}+a_{1}|x_{2}|^{2}\end{bmatrix}.$

For $x_{1}=0$, this matrix clearly is positive semidefinite. Hence assume
$x_{1}\neq 0$. In that case the Schur complement of the above matrix with
respect to the left upper corner is

$\displaystyle
b_{2}|x_{1}|^{2}+a_{1}|x_{2}|^{2}-\frac{|a_{1}x_{1}{\overline{x}}_{2}-2a_{1}x_{2}{\overline{x}}_{1}|^{2}}{a_{1}|x_{1}|^{2}}=$
$\displaystyle\qquad=b_{2}|x_{1}|^{2}+a_{1}|x_{2}|^{2}-\frac{1}{a_{1}}\left|a_{1}\frac{x_{1}}{|x_{1}|}{\overline{x}}_{2}-2a_{1}x_{2}\frac{{\overline{x}}_{1}}{|x_{1}|}\right|^{2}.$

For ${\mathbb{F}}={\mathbb{C}}$ there are $x\in{\mathbb{C}}^{2}$ where this