1289

INFEASIBILITY OF CONSTRUCTING A SPECIAL

ORTHOGONAL MATRIX FOR THE DETERMINISTIC REMOTE

PREPARATION STATE OF AN ARBITRARY N-QUBIT STATE

WENJIE LIU

Engineering Research Center of Digital Forensics, Ministry of Education,

Nanjing University of Information Science and Technology,

Nanjing, 210044, China

School of Computer and Software, Nanjing University of Information Science and
Technology,

Nanjing, 210044, China

<EMAIL_ADDRESS>
ZIXIAN LI

School of Computer and Software, Nanjing University of Information Science and
Technology,

Nanjing, 210044, China

<EMAIL_ADDRESS>
GONGLIN YUAN

School of Mathematics and Information Science, Center for Applied Mathematics
of Guangxi,

Guangxi University, Nanning, 530004, China

<EMAIL_ADDRESS>
Received July 9, 2022
Revised October 8, 2022

In this paper, we present a polynomial-complexity algorithm to construct a
special orthogonal matrix for the deterministic remote state preparation
(DRSP) of an arbitrary $n$-qubit state, and prove that if $n>3$, such matrices
do not exist. Firstly, the construction problem is split into two sub-
problems, i.e., finding a solution of a semi-orthogonal matrix and generating
all semi-orthogonal matrices. Through giving the definitions and properties of
the matching operators, it is proved that the orthogonality of a special
matrix is equivalent to the cooperation of multiple matching operators, and
then the construction problem is reduced to the problem of solving an XOR
linear equation system, which reduces the construction complexity from
exponential to polynomial level. Having proved that each semi-orthogonal
matrix can be simplified into a unique form, we use the proposed algorithm to
confirm that the unique form does not have any solution when $n>3$, which
means it is infeasible to construct such a special orthogonal matrix for the
DRSP of an arbitrary $n$-qubit state.

Keywords: Quantum information, remote state preparation, arbitrary $n$-qubit
state, orthogonal matrix

##  1 Introduction

Remote state preparation (RSP)[1, 2, 3, 4] is a method for quantum state
transmission via quantum entanglement in which several classical channels are
required. In RSP, the sender (known as Alice) knows the state to be sent but
does not need to prepare it. RSP is an important issue in the field of quantum
information because of the lower cost of classical communication, and various
RSP schemes of a quantum state with a certain number of qubits, such as a
single-qubit state[5, 6, 7, 8, 9], two-qubit state[10, 11, 12], three-qubit
state[13, 14, 15, 16, 17], four-qubit state[18, 19, 20, 21], and five-qubit
state[22], have been proposed. In addition, since the theoretical probability
of success is $100\%$, deterministic RSP (DRSP) schemes[7, 11, 14, 15, 20, 21,
22] are more concerned than probabilistic ones[6, 13, 17, 19].

For the sake of generality, several DRSP schemes of an arbitrary $n$-qubit
state (here, “arbitrary” means any number of qubits) are proposed[23, 24, 25,
26, 27, 28]. There is a similar and key element in all of them: a kind of
special $2^{n}\times 2^{n}$ real-parameter orthogonal matrices, where each
column is consisted of permutations of real coefficients $\pm a_{0},\pm
a_{1},\cdots,\pm a_{2^{n}-1}$ of the prepared state. These matrices have been
used in several schemes[11, 14, 15, 19] for a certain number of qubits, and
all of them are constructed through accidental patchwork or violent traversal.
For an arbitrary $n$, it is necessary to design a general method to construct
such a special orthogonal matrix. In 2018, Wei et al.[23] proposed an
algorithm to construct such a matrix for an arbitrary $n$ that limits the
traversal range, but it is essentially still an exponential violent traversal.
In this paper, we present an polynomial-complexity general algorithm to
construct such a matrix for the DRSP of an arbitrary $n$-qubit state, where
the construction problem is reduced to the problem of solving an XOR linear
equation system. In addition, we prove that such special orthogonal matrices
do not exist for $4$ or more qubits through proving that each semi-orthogonal
matrix (formally defined in the text) can be simplified into a unique form and
then using the proposed algorithm to confirm that the unique form does not
have any solution. As a result, we prove that it is infeasible to construct
such a orthogonal matrix for the DRSP of an arbitrary $n$-qubit state.

The rest of this paper is organized as follows: in Section 2, these schemes
are briefly reviewed and analyzed. The problem of constructing a special
orthogonal matrix is defined and split in Section 3. The construction
algorithm is presented in Section 4. The infeasibility proof is presented in
Section 5. We conclude the paper in Section 6.

##  2 Schemes review and analysis

In this section, we briefly review the DRSP of a real-parameter state via
maximally two-qubit states as a representative of the above schemes and focus
on the review and analysis of Wei et al.s’ algorithm[23].

###  2.1 DRSP of a real-parameter state via maximally two-qubit states

Assume a sender Alice and a receiver Bob both have a set of $n$ particles
respectively, where the particles $j=1,3,5,\cdots,2n-1$ belong to Alice and
$k=2,4,6,\cdots,2n$ to Bob. There is a quantum entanglement between each
particle pair $(j,k)$ held by Alice and Bob, respectively. Each of these pairs
forms a maximally two-qubit entangled state which can be

$\left|\Psi\right\rangle_{jk}=\frac{1}{\sqrt{2}}\left(\left|00\right\rangle+\left|11\right\rangle\right)_{jk},j=1,3,\cdots,2n-1,k=2,4,\cdots,2n\,.$
(1)

or other similar Bell states. Thus, we have a total state as
$\left|\Psi\right\rangle_{total}=\left|\Psi\right\rangle_{12}\otimes\left|\Psi\right\rangle_{34}\otimes\cdots\otimes\left|\Psi\right\rangle_{(2n-1)2n}$.
Now Alice wants to transmit a state
$\left|\psi\right\rangle=\sum_{i=0}^{2^{n}-1}a_{i}e^{\imath\varphi_{i}}\left|i\right\rangle$
called an arbitrary $n$-qubit general state, where $\imath$ is the imaginary
unit, $a_{i}$, $\varphi_{i}$ are all arbitrary real numbers and
$\sum_{i=0}^{2^{n}-1}a_{i}^{2}=1$. The follows are the general processes of
the RSP via maximally two-qubit states.

Step 1 Alice needs to find a special projective measurement basis
$\\{\left|\tau_{i}\right\rangle|i=0,1,\cdots,2^{n}-1\\}$ in the Hilbert space
of the particles $j$. Therefore, the total state can be written as

$\left|\Psi\right\rangle_{total}=\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{2^{n}-1}\left|\tau_{i}\right\rangle_{13\cdots(2n-1)}\otimes\left|\theta_{i}\right\rangle_{24\cdots
2n},$ (2)

where

$\left|\theta_{i}\right\rangle_{B}=\left|\tau_{i}\right\rangle_{A}^{\dagger}\otimes\left|\Psi\right\rangle_{AB},i=0,1,\cdots,2^{n}-1$
(3)

is a basis in Hilbert space of particles $k$. Now Alice needs to measure her
particles on the measurement basis
$\left\\{\left|\tau_{i}\right\rangle\right\\}$.

Step 2 After the measurement, Bob’s particles will collapse into
$\left\\{\left|\theta_{i}\right\rangle\right\\}$ where $i$ is one of the $16$
results. Meanwhile, Alice informs the measurement result $i$ to Bob via
classical channels.

Step 3 According to the value of $i$, Bob needs to select a previously agreed
unitary operator $U_{i}$ to act on $\left|\theta_{i}\right\rangle$, to restore
the target state $\left|\psi\right\rangle$, i.e.,
$U_{i}\left|\theta_{i}\right\rangle=\left|\psi\right\rangle$.

In the last step, we should recover the target state $\left|\psi\right\rangle$
by using the unitary operator $U_{i}$ independent of
$\left|\psi\right\rangle$. For an arbitrary $n$-qubit state it is hard to
realize with a high success probability, e.g., if letting
$\left|\tau_{0}\right\rangle=\left|\psi\right\rangle$, then only in the case
of $i=0$, it can be recovered by using Pauli operators with a probability
$\frac{1}{16}$[19].

If only considering a real-parameter state, i.e.,
$\left|\psi\right\rangle=\sum_{i=0}^{2^{n}-1}a_{i}\left|i\right\rangle$, it is
proposed[23] to use a complete orthogonal basis
$\left|\tau_{i}\right\rangle=U[\Theta_{n}^{n}]\begin{pmatrix}\left|0\right\rangle,\left|1\right\rangle,\cdots,\left|2^{n}-1\right\rangle\end{pmatrix}^{T}$,
where the elements of the $2^{n}\times 2^{n}$ orthogonal matrix
$U[\Theta_{n}^{n}]$ are consisted of permutations of $\pm a_{0},\pm
a_{1},\cdots,\pm a_{2^{n}-1}$. Thus, the $\left|\psi\right\rangle$ in the
above scheme can be recovered by simply element-rearranging and phase-
inversion. If any above orthogonal matrix $U[\Theta_{n}^{n}]$ is constructed,
then the RSP of an arbitrary $n$-qubit real-parameter state can be realized
simply with a probability of $100\%$.

Although the above scheme is only applicable to the DRSP of a real-parameter
state, there are also several DRSP schemes[24, 26, 27, 28] of a general state
that use the above orthogonal matrix. Therefore, the construction of such an
orthogonal matrix is a key point to realize the DRSP of an arbitrary $n$-qubit
state.

###  2.2 Wei et al.’s algorithm to construct a special orthogonal matrix

Wei et al.[23] proposed an algorithm to construct an above orthogonal
$2^{n}\times 2^{n}$ matrix $U[\Theta^{n}_{n}]$ as follows.

Step 1 Set the elements of the $1$st and $(2^{n-1}+1)$th rows together with
the $1$st and $(2^{n-1}+1)$th columns

$U[\Theta_{n}^{n}]=\begin{pmatrix}a_{0}&a_{1}&\cdots&a_{2^{n-1}-1}&a_{2^{n-1}}&a_{2^{n-1}+1}&\cdots&a_{2^{n}-1}\\\
a_{1}&{\color[rgb]{1,0,0}\ddots}&{\color[rgb]{1,0,0}\cdots}&{\color[rgb]{1,0,0}\cdots}&a_{2^{n-1}+1}&{\color[rgb]{0,0,1}\cdots}&{\color[rgb]{0,0,1}\cdots}&{\color[rgb]{0,0,1}\cdots}\\\
\vdots&{\color[rgb]{1,0,0}\vdots}&{\color[rgb]{1,0,0}\ddots}&{\color[rgb]{1,0,0}\cdots}&\cdots&{\color[rgb]{0,0,1}\cdots}&{\color[rgb]{0,0,1}\cdots}&{\color[rgb]{0,0,1}\cdots}\\\
a_{2^{n-1}-1}&{\color[rgb]{1,0,0}\vdots}&{\color[rgb]{1,0,0}\vdots}&{\color[rgb]{1,0,0}\ddots}&a_{2^{n}-1}&{\color[rgb]{0,0,1}\cdots}&{\color[rgb]{0,0,1}\cdots}&{\color[rgb]{0,0,1}\cdots}\\\
a_{2^{n-1}}&-a_{2^{n-1}+1}&\vdots&-a_{2^{n}-1}&-a_{0}&a_{1}&\cdots&a_{2^{n-1}-1}\\\
a_{2^{n-1}+1}&{\color[rgb]{0,1,0}\vdots}&{\color[rgb]{0,1,0}\vdots}&{\color[rgb]{0,1,0}\vdots}&-a_{1}&{\color[rgb]{0,0,1}\ddots}&{\color[rgb]{0,0,1}\cdots}&{\color[rgb]{0,0,1}\cdots}\\\
\vdots&{\color[rgb]{0,1,0}\vdots}&{\color[rgb]{0,1,0}\vdots}&{\color[rgb]{0,1,0}\vdots}&\vdots&{\color[rgb]{0,0,1}\vdots}&{\color[rgb]{0,0,1}\ddots}&{\color[rgb]{0,0,1}\cdots}\\\
a_{2^{n}-1}&{\color[rgb]{0,1,0}\vdots}&{\color[rgb]{0,1,0}\vdots}&{\color[rgb]{0,1,0}\vdots}&-a_{2^{n-1}-1}&{\color[rgb]{0,0,1}\vdots}&{\color[rgb]{0,0,1}\vdots}&{\color[rgb]{0,0,1}\ddots}\end{pmatrix}.$
(4)

When $n=1$, we can obtain the matrix $U[\Theta^{1}_{1}]$ from this step, and
the following processes would be ignored.

Step 2 If $n\leq 2$, then set that
$U[\Theta^{n}_{n}](i,j)=U[\Theta^{n-1}_{n-1}](i,j)$, here $2\leq i,j\leq
2^{n-1}$. The parameter $U[\Theta^{n}_{n}](i,j)$ presents the element in the
$i$th row and $j$th column of the matrix $U[\Theta^{n}_{n}]$. After that, the
red items on the above equation can be determined.

Step 3 According to this equation
$\sum_{i=1}^{2^{n}}U[\Theta^{n}_{n}](i,j)\cdot
U[\Theta^{n}_{n}](i,2^{n-1}+1)=0(j\leq 2^{n-1})$, we can obtain the elements
from the $1$st column to $2^{n-1}$th column, i.e., the green elements of
$U[\Theta^{n}_{n}](i,j)$ could be calculated.

Step 4 Based on $\sum_{i=1}^{2^{n}}U[\Theta^{n}_{n}](i,j)\cdot
U[\Theta^{n}_{n}](i,k)=0(k=1,2^{n-1}+1,2\leq j\leq 2^{n})$ the elements from
the $1$st column to $2^{n}$th column could be completed; namely, the blue
elements of the matrix $U[\Theta^{n}_{n}](i,j)$ can be fulfilled.

###  2.3 Analysis of Wei et al.’s algorithm

As can be seen, the last two steps of the above algorithm do not give clear
execution steps, but only the constraints of the solution, which is
essentially a violent traversal. Let $N=2^{n}$. Even if the element
arrangement is determined, it needs to traverse
$2^{\left(\frac{N}{2}-1\right)^{2}}+2^{2\left(\frac{N}{2}-1\right)^{2}}=O(2^{\frac{N^{2}}{2}})$
times to determine the distribution of minus signs in the worst case, because
those signs can be regarded as Boolean variables. As an instance, let $n=4$,
i.e., $N=16$, then we need to traverse
$2^{\left(\frac{16}{2}-1\right)^{2}}+2^{2\left(\frac{16}{2}-1\right)^{2}}\approx
3.169\times 10^{29}$ times at worst, which is impossible. Therefore, for the
RSP with a large $n$ ($n>3$), the algorithm needs unimaginable time.

In fact, we will prove that for $n>3$ the above orthogonal matrix does not
exist, which means that the above algorithm will not output any solution. To
prove it, we will first propose a more efficient construction algorithm with
polynomial time and space complexity for $N$.

##  3 Problem definition and split of constructing a special orthogonal matrix

In this section, we will define the problem of constructing an above
orthogonal matrix as Problem 1 in Section 3.1 and split it into two sub-
problems as Problem 2 and Problem 3 in Section 3.2.

###  3.1 Problem definition

We define the construction problem as follows.

######  Definition 1 (Special orthogonal matrix)

Given a set $U=\left\\{a_{0},a_{1},\cdots,a_{15}\right\\}$ of real parameters
of size $N$, where $N$ is a positive integer power of 2 and
$\sum_{i=0}^{N-1}a_{i}^{2}=1$. A special orthogonal matrix $S_{N}$ is an
orthogonal matrix, where each column vector $\textbf{{s}}^{(i)}$ is obtained
by adding positive and negative signs to the elements of $U$ and arranging
them arbitrarily without repeating them, i.e.,
$\textbf{{s}}^{(i)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0i}}a_{\alpha_{0i}},\left(-1\right)^{\sigma_{1i}}a_{\alpha_{1i}},\cdots,\left(-1\right)^{\sigma_{(N-1)i}}a_{\alpha_{(N-1)i}}\end{pmatrix}^{T}$
where $\left\\{\alpha_{0i},\alpha_{1i},\cdots,\alpha_{(N-1)i}\right\\}$ is a
permutation of index sequence
$\left[N\right]=\left\\{0,1,\cdots,N-1\right\\}$, and
$\sigma_{0i},\sigma_{1i},\cdots,\sigma_{(N-1)i}$ are each valued as $0,1$,
e.g.,
$\textbf{{s}}=\begin{pmatrix}-a_{1},a_{0},-a_{3},-a_{2},\cdots,-a_{N-2}\end{pmatrix}^{T}$.

###### Problem 1

(Construct a special orthogonal matrix) Given a set of real parameters $U$ of
size $N$ where $N$ is a positive integer power of $2$ and
$\sum_{i=0}^{N-1}a_{i}^{2}=1$, construct an $N$-order special orthogonal
matrix.

###  3.2 Problem split

We have a definition as follows.

######  Definition 2 (Semi-orthogonal matrix)

An $N$-order matrix $\left|S_{N}\right|$ is a semi-orthogonal matrix if:

  * $\bullet$

Each column vector
$\textbf{{s}}^{(i)}=\begin{pmatrix}a_{\alpha_{0i}},a_{\alpha_{1i}},\cdots,a_{\alpha_{(N-1)i}}\end{pmatrix}^{T}$,
where $\left\\{\alpha_{0i},\alpha_{1i},\cdots,\alpha_{(N-1)i}\right\\}$ is a
permutation of index sequence $\left[N\right]$.

  * $\bullet$

For any two column vectors $\textbf{{s}}^{(i)},\textbf{{s}}^{(j)}$, all
elements in $\textbf{{s}}^{(i)}$ can be divided into several $2$-tuples, and
in $\textbf{{s}}^{(j)}$, the elements in each $2$-tuple are and only
exchanged.

In addition, if for a subset $V$ of $U$, a matrix $\left|S_{V}\right|$ of
order $\left|V\right|$ satisfies the above description, then it is also called
semi-orthogonal.

The following basic proposition can be given.

###### Proposition 1

Given two column vectors

$\begin{aligned}
\textbf{{s}}^{(i)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0i}}a_{\alpha_{0i}}\\\
\left(-1\right)^{\sigma_{1i}}a_{\alpha_{1i}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)i}}a_{\alpha_{(N-1)i}}\end{pmatrix},\textbf{{s}}^{(j)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0j}}a_{\alpha_{0j}}\\\
\left(-1\right)^{\sigma_{1j}}a_{\alpha_{1j}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)j}}a_{\alpha_{(N-1)j}}\end{pmatrix}\end{aligned},$
(5)

then the necessary and sufficient condition for
$\textbf{{s}}^{(i)}\perp\textbf{{s}}^{(j)}$ is that all elements of
$\textbf{{s}}^{(i)}$ can be divided into several $2$-tuples, and in
$\textbf{{s}}^{(j)}$, the elements in each 2-tuple are exchanged and one of
them is multiplied by $-1$. i.e.,

  * $\bullet$

$\forall k\in\left[N\right]$, $\alpha_{ki}\neq\alpha_{kj}$;

  * $\bullet$

$\forall k,l\in\left[N\right]$ and $k\neq l$, if $\alpha_{ki}=\alpha_{lj}$,
then $\alpha_{li}=\alpha_{kj}$ and
$\sigma_{ki}\oplus\sigma_{kj}=\sigma_{li}\oplus\sigma_{lj}\oplus 1$, where
“$\oplus$” means XOR.

Proof:

  * $\bullet$

(Sufficiency) $\forall k\in\left[N\right]$, it must be able to find
$l\in\left[N\right]$ and $l\neq k$ so that $\alpha_{ki}=\alpha_{lj}$, because
$\left\\{\alpha_{ki}|k\in\left[N\right]\right\\}$ and
$\left\\{\alpha_{lj}|l\in\left[N\right]\right\\}$ are both permutations of
$\left[N\right]$.
Without loss of generality, if $\alpha_{ki}=\alpha_{lj}$, then
$\alpha_{li}=\alpha_{kj}$ and
$\sigma_{ki}\oplus\sigma_{kj}=\sigma_{li}\oplus\sigma_{lj}\oplus 1$, thus in
the inner product expression of $\textbf{{s}}^{(i)},\textbf{{s}}^{(j)}$, there
must be a term

$\displaystyle\left(-1\right)^{\sigma_{ki}}a_{\alpha_{ki}}\left(-1\right)^{\sigma_{kj}}a_{\alpha_{kj}}+\left(-1\right)^{\sigma_{li}}a_{\alpha_{li}}\left(-1\right)^{\sigma_{lj}}a_{\alpha_{lj}}$
(6)
$\displaystyle=\left(-1\right)^{\sigma_{ki}\oplus\sigma_{kj}}a_{\alpha_{ki}}a_{\alpha_{kj}}+\left(-1\right)^{\sigma_{li}\oplus\sigma_{lj}}a_{\alpha_{li}}a_{\alpha_{lj}}$
$\displaystyle=\left(-1\right)^{\sigma_{li}\oplus\sigma_{lj}\oplus
1}a_{\alpha_{li}}a_{\alpha_{lj}}+\left(-1\right)^{\sigma_{li}\oplus\sigma_{lj}}a_{\alpha_{li}}a_{\alpha_{lj}}$
$\displaystyle=\left(-1\right)^{\sigma_{li}\oplus\sigma_{lj}}a_{\alpha_{li}}a_{\alpha_{lj}}\left(-1+1\right)$
$\displaystyle=0.$

It is consistent for each $2$-tuple in $\textbf{{s}}^{(i)}$, so the inner
product $\textbf{{s}}^{(i)\dagger}\textbf{{s}}^{(j)}=0$, i.e.,
$\textbf{{s}}^{(i)}\perp\textbf{{s}}^{(j)}$.

  * $\bullet$

(Necessity) Without losing generality, suppose $\alpha_{ki}=\alpha_{kj}$, then
there is a term $\pm\alpha_{ki}\alpha_{kj}$ in the inner product expression
without any corresponding term $\mp\alpha_{ki}\alpha_{kj}$ because elements in
a permutation cannot be repeated. Thus, for any element values, the inner
product of $\textbf{{s}}^{(i)},\textbf{{s}}^{(j)}$ cannot be guaranteed to be
0, so $\forall k\in\left[N\right]$, $\alpha_{ki}\neq\alpha_{kj}$.

Assume $\alpha_{ki}=\alpha_{lj}$ where $k\neq l$. There must be a term
$\left(-1\right)^{\sigma_{ki}\oplus\sigma_{kj}}a_{\alpha_{ki}}a_{\alpha_{kj}}+\left(-1\right)^{\sigma_{li}\oplus\sigma_{lj}}a_{\alpha_{li}}a_{\alpha_{lj}}$
in the inner product expression $\textbf{{s}}^{(i)\dagger}\textbf{{s}}^{(j)}$.
Since the elements are valued arbitrarily,
$\left(-1\right)^{\sigma_{ki}\oplus\sigma_{kj}}a_{\alpha_{ki}}a_{\alpha_{kj}}$
must correspond to $\left(-1\right)^{\sigma_{ki}\oplus\sigma_{kj}\oplus
1}a_{\alpha_{ki}}a_{\alpha_{kj}}$ to be offset into $0$. Because
$\alpha_{ki}=\alpha_{lj}$, if $\alpha_{li}=\alpha_{kj}$ and
$\sigma_{ki}\oplus\sigma_{kj}=\sigma_{li}\oplus\sigma_{lj}\oplus 1$, then
$\left(-1\right)^{\sigma_{li}\oplus\sigma_{lj}}a_{\alpha_{li}}a_{\alpha_{lj}}=\left(-1\right)^{\sigma_{ki}\oplus\sigma_{kj}\oplus
1}a_{\alpha_{ki}}a_{\alpha_{kj}}$, which can be offset by
$\left(-1\right)^{\sigma_{ki}\oplus\sigma_{kj}}a_{\alpha_{ki}}a_{\alpha_{kj}}$;
if $\alpha_{li}\neq\alpha_{kj}$, it’s impossible to find another term
$a_{\alpha_{mi}}a_{\alpha_{mj}}=a_{\alpha_{ki}}a_{\alpha_{kj}}$ because
$\forall m\in\left[N\right]$, $a_{\alpha_{mj}}\neq
a_{\alpha_{lj}}=a_{\alpha_{ki}}$, and $a_{\alpha_{mj}}\neq a_{\alpha_{kj}}$.
Thus, $\alpha_{li}=\alpha_{kj}$ and
$\sigma_{ki}\oplus\sigma_{kj}=\sigma_{li}\oplus\sigma_{lj}\oplus 1$ hold
$\Box$.

###### Remark 1

  * $($i$)$

According to Proposition 1, the process of obtaining another orthogonal column
vector $b$ from one column vector $a$ is as follows: divide the elements in
$a$ into several $2$-tuples, and for each $2$-tuple, exchange the elements and
multiply one of them by $-1$.

  * $($ii$)$

By (i), if removing the signs of all the elements of a special orthogonal
matrix $S$, it obviously becomes a semi-orthogonal matrix, denoted as
$\left|S\right|$. However, a semi-orthogonal matrix may correspond to one or
more special orthogonal matrices, or even not to any special orthogonal
matrix.

  * $($iii$)$

Most schemes using special orthogonal matrices choose to piece up them by
using smaller blocks, e.g., Wei et al.’s scheme[23]. For example, the
$2^{n}\times 2^{n}$ matrix in Eq. (4) can be pieced up by $4$ smaller
$2^{\frac{n}{2}}\times 2^{\frac{n}{2}}$ orthogonal matrices. However, it
should be considered that the elements arrangement of a special orthogonal
matrix is out of order, and the feasibility of constructing without using
blocks has not been logically denied. We will prove that the method based on
blocks is universal because all special orthogonal matrices can be simplified
into forms pieced up by blocks.

As shown in Remark 1, each special orthogonal matrix corresponds to a semi-
orthogonal matrix. If we have a general method to determine whether a semi-
orthogonal matrix has a solution (i.e., the corresponding special orthogonal
matrix), and generate all semi-orthogonal matrices, then we can determine
whether each semi-orthogonal matrix has a solution, so as to find at least one
special orthogonal matrix, or deny its existence. In fact, for the case of
$n>3$, there is indeed no solution for each $N$-order semi-orthogonal matrix,
which is proved in Section 5. Therefore, Problem 1 can be split into the
following two sub-problems.

###### Problem 2

(Find a solution of a semi-orthogonal matrix) Given any $N$-order semi-
orthogonal matrix, find one of the corresponding special orthogonal matrices.

###### Problem 3

(Generate all semi-orthogonal matrices) Given a positive integer $n$, generate
all $2^{n}$-order semi-orthogonal matrices.

Problem 2 will be solved in Section 4, while Problem 3 will be solved in
Section 5.

##  4 Proposed algorithm to construct a special orthogonal matrix

In this section, we present the algorithm for Problem 2. This section is
arranged as follows: in Section 4.1, we define the matching operator and show
several property of it. It is proved that the orthogonality of every two
vectors in a special orthogonal matrix is equivalent to the cooperation of
their matching operators, and thus to the the establishment of several
matching equations in Section 4.2, and then Problem 2 is reduced to the
problem of solving an XOR linear equation system in Section 4.3. The
construction algorithm is presented also in Section 4.3.

###  4.1 Matching operator

We have the following definitions.

######  Definition 3 (Matching operation)

Since the elements in a column vector are one-to-one corresponding to the row
indexes, the process of obtaining another orthogonal column vector $b$ from
one column vector $a$ is equivalent to dividing $N$ row indexes in $a$ into
$\frac{N}{2}$ row index $2$-tuples, and for each $2$-tuple, exchanging the two
rows and multiplying one row of them by $-1$. We call the above operation a
matching operation.

######  Definition 4 (Couple)

A couple $\left\langle i,j\right\rangle$ is defined as an operation that
exchanges two rows $i,j$ of a column vector and then multiplies one of them by
$-1$. A Boolean variable for each couple is defined: $\left\langle
i,j\right\rangle=0,1$, where $0$ means multiplying the row $i$ (i.e., the
previous $j$) by $-1$ after the exchanging, and $1$ means the opposite.

######  Definition 5 (Division)

A matching operation $M$ is always a combination of $\frac{N}{2}$ couples that
do not overlap, and the set $D(M)$ of these couples is defined as the division
of $M$.

######  Definition 6 (Scattered matrix)

A square matrix is called a scattered matrix, if in each row or column there
is only one $\pm 1$, and the other elements are $0$. These $\pm 1$ are called
scattered points.

###### Remark 2

  * $($i$)$

The value of a couple $\left\langle i,j\right\rangle$ means a “pointing”,
i.e., $0$ points to $i$ and $1$ points to $j$. We denote multiplying row $i$
by $-1$ as $-i$ (e.g., $i\mapsto j$ means mapping $i$ to $j$ and then
multiplying the new $j$ by $-1$), then there are two mappings:
$i\overset{\left\langle i,j\right\rangle}{\mapsto}{(-1)}^{\left\langle
i,j\right\rangle}j,j\overset{\left\langle
j,i\right\rangle}{\mapsto}{(-1)}^{\left\langle j,i\right\rangle}i$, where
$\left\langle i,j\right\rangle$ and $\left\langle j,i\right\rangle$ describe
the same operation, denoted as $\left\langle
i,j\right\rangle\equiv\left\langle j,i\right\rangle$. Obviously, $\left\langle
i,j\right\rangle=\left\langle j,i\right\rangle\oplus 1$.

  * $($ii$)$

$\overline{\left\langle i,j\right\rangle}$ is defined as a new couple meaning
exchanging rows $i,j$ as well but multiplying the row contrary to
$\left\langle i,j\right\rangle$ by $-1$, i.e., $\overline{\left\langle
i,j\right\rangle}=\left\langle i,j\right\rangle\oplus 1$. Note no thinking
that $\overline{\left\langle i,j\right\rangle}\equiv\left\langle
j,i\right\rangle$.

  * $($iii$)$

One couple $\left\langle i,j\right\rangle$ always corresponds to one bijection
$\sigma:\left\\{i\right\\}\leftrightarrow\left\\{j\right\\}$, but one
bijection $\sigma$ corresponds to two couples: $\left\langle i,j\right\rangle$
and $\overline{\left\langle i,j\right\rangle}$. If the operation of
multiplying $-1$ is not considered, the couple $\left\langle i,j\right\rangle$
can be considered as the bijection $\sigma$.

  * $($iv$)$

A couple $\left\langle i,j\right\rangle$ one-to-one corresponds to an
$N$-order matrix $E_{\left\langle i,j\right\rangle}(-1)E(i,j)$, where $E(i,j)$
is a row-exchanging matrix and $E_{\left\langle i,j\right\rangle}(-1)$ is a
row-multiplying matrix that multiplies the row pointed by $\left\langle
i,j\right\rangle$ ($0$ points to $i$, $1$ points to $j$) by $-1$. Note that
$E(i,j)$ and $E_{\left\langle i,j\right\rangle}(-1)$ are both scattered
matrices.

A matching operation $M$ one-to-one corresponds to an $N$-order matrix, i.e.,
the product of some elementary matrices as

$M=\prod_{\left\langle i,j\right\rangle\in D(M)}\left[E_{\left\langle
i,j\right\rangle}(-1)E(i,j)\right]=\prod_{\left\langle i,j\right\rangle\in
D(M)}E_{\left\langle i,j\right\rangle}(-1)\prod_{\left\langle
i,j\right\rangle\in D(M)}E(i,j),$ (7)

which called the matching operator corresponding to the matching operation. By
Proposition 1, if a matching operator $M$ can be found such that the column
vector $b=Ma$, then $b\perp a$; conversely, if $b\perp a$, a corresponding
matching operator $M$ can be found.

We have the following proposition about some properties of matching operators,
which will be widely used.

###### Proposition 2

The following properties of a matching operator $M$ hold:

  * $($i$)$

(Anti-self-reversibility) $M^{-1}=-M$;

  * $($ii$)$

(Anti-symmetry) $M^{T}=-M$, and all elements on the main diagonal of $M$ are
$0$;

  * $($iii$)$

$-M$ is also a matching operator;

  * $($iv$)$

A scattered matrix must be a matching operator if it’s anti-self-reversible or
anti-symmetric.

To prove the above proposition, we first need the following lemmas.

###### Lemma 1

The following equations hold:

  * $($i$)$

$E(i,j)^{2}=E_{\left\langle i,j\right\rangle}(-1)^{2}=I$,

  * $($ii$)$

$E(i,j)E_{\left\langle i,j\right\rangle}(-1)=E_{\overline{\left\langle
i,j\right\rangle}}(-1)E(i,j)$,

  * $($iii$)$

$\prod_{\left\langle i,j\right\rangle\in D(M)}E_{\left\langle
i,j\right\rangle}(-1)\prod_{\left\langle i,j\right\rangle\in
D(M)}E_{\overline{\left\langle i,j\right\rangle}}(-1)=-I$.

where $I$ is the identity matrix and $M$ is a matching operator.

Proof:

  * $($i$)$

Obviously according to the definition of the elementary matrix.

  * $($ii$)$

Assume $\left\langle i,j\right\rangle=0$, then $E(i,j)E_{\left\langle
i,j\right\rangle}(-1)$ means multiplying by $-1$ to $i$ and then exchanging
$i$ to $j$, and $E_{\overline{\left\langle i,j\right\rangle}}(-1)E(i,j)$ means
exchanging $i$ to $j$ and then multiplying by $-1$ to the new $j$, which are
the same. Similarly in the case of $\left\langle i,j\right\rangle=1$.

  * $($iii$)$

For each couple $\left\langle i,j\right\rangle$, $E_{\left\langle
i,j\right\rangle}(-1)E_{\overline{\left\langle i,j\right\rangle}}(-1)$ means
multiplying by $-1$ for the two rows $i,j$. Consider all couples in $D(M)$,
then each row is multiplied by $-1$, i.e., the operation is equivalent to $-I$
$\Box$.

###### Lemma 2

The following properties of a scattered matrix $A$ hold:

  * $($i$)$

If $B$ is also a scattered matrix, then $AB$ is still scattered.

  * $($ii$)$

$A$ is orthogonal.

Proof:

  * $($i$)$

$\forall i$, there is a scattered point $(i,j)$ in $A$ and $(j,k)$ in $B$,
thus $(i,k)$ in $AB$. Similarly, $\forall k$, there is a scattered point
$(i,k)$ in $B$. $\forall i$, there is not any other scattered point
$(i,j^{\prime})$ in $A$, not any $(j,k^{\prime})$ in $B$, thus not any
$(i,k^{\prime})$ in $AB$. Similarly, there is not any other scattered point
$(i^{\prime},k)$ in $AB$. Therefore, each row or column in $AB$ has only one
scattered point, so $AB$ is a scattered matrix.

  * $($ii$)$

The inner product between every two column vectors of the scattered matrix $A$
is $0$, and each column vector is a unit vector, so $A$ is orthogonal, i.e.,
$A^{-1}=A^{T}$ $\Box$.

By Lemma 2 and Eq. (7), any matching operator $M$ is a scattered matrix as
well. Therefore, we can prove Proposition 2.

Proof of Proposition 2:

  * $($i$)$

Let matching $M=\prod_{\left\langle i,j\right\rangle\in D(M)}E_{\left\langle
i,j\right\rangle}(-1)\prod_{\left\langle i,j\right\rangle\in D(M)}E(i,j)$. By
Lemma 1, then

$\begin{aligned} &MM=\left[\prod_{\left\langle i,j\right\rangle\in
D(M)}E_{\left\langle i,j\right\rangle}(-1)\prod_{\left\langle
i,j\right\rangle\in D(M)}E(i,j)\right]\left[\prod_{\left\langle
i,j\right\rangle\in D(M)}E_{\left\langle
i,j\right\rangle}(-1)\prod_{\left\langle i,j\right\rangle\in
D(M)}E(i,j)\right]\\\ &=\left[\prod_{\left\langle i,j\right\rangle\in
D(M)}E_{\left\langle i,j\right\rangle}(-1)\prod_{\left\langle
i,j\right\rangle\in D(M)}E_{\overline{\left\langle
i,j\right\rangle}}(-1)\right]\left[\prod_{\left\langle i,j\right\rangle\in
D(M)}E(i,j)\prod_{\left\langle i,j\right\rangle\in D(M)}E(i,j)\right]\\\
&=-I\end{aligned},$ (8)

thus $M^{-1}=-M$.

  * $($ii$)$

By Lemma 2 and (i), $M^{T}=M^{-1}=-M$. If there was any non-zero element on
the main diagonal of $M$, then $M^{T}\neq-M$, which causes a contradiction.

  * $($iii$)$

Assume matching operator $\overline{M}$ where
$D(\overline{M})=\left\\{\overline{\left\langle i,j\right\rangle}|\left\langle
i,j\right\rangle\in D(M)\right\\}$, then by Lemma 1 and Eq. (7) we have

$\begin{aligned} &-M=-\prod_{\left\langle i,j\right\rangle\in
D(M)}E_{\left\langle i,j\right\rangle}(-1)\prod_{\left\langle
i,j\right\rangle\in D(M)}E(i,j)\\\ &=\left[\prod_{\left\langle
i,j\right\rangle\in D(M)}E_{\overline{\left\langle
i,j\right\rangle}}(-1)\prod_{\left\langle i,j\right\rangle\in
D(M)}E_{\left\langle i,j\right\rangle}(-1)\right]\left[\prod_{\left\langle
i,j\right\rangle\in D(M)}E_{\left\langle
i,j\right\rangle}(-1)\prod_{\left\langle i,j\right\rangle\in
D(M)}E(i,j)\right]\\\ &=\prod_{\left\langle i,j\right\rangle\in
D(M)}E_{\overline{\left\langle i,j\right\rangle}}(-1)\prod_{\left\langle
i,j\right\rangle\in D(M)}E(i,j)\\\ &=\prod_{\overline{\left\langle
i,j\right\rangle}\in D(\overline{M})}E_{\overline{\left\langle
i,j\right\rangle}}(-1)\prod_{\overline{\left\langle i,j\right\rangle}\in
D(\overline{M})}E(i,j)\\\ &=\overline{M}\end{aligned},$ (9)

thus $-M$ is also a matching operator.

  * $($iv$)$

For any scattered matrix $A$, by Lemma 2 we have $A^{-1}=A^{T}$, thus its’
anti-self-reversibility and anti-symmetry are equivalent: $A^{-1}=A^{T}=-A$.
Let $A$ be anti-symmetric, for every two anti-symmetrical elements in $A$, we
exchange them, and multiply the row where $-1$ is by $-1$, then we get the
identity matrix $I$. The above operations define $\frac{N}{2}$ couples and a
set $D$ of these couples, then we have $\prod_{\left\langle
i,j\right\rangle\in D}E_{\left\langle i,j\right\rangle}(-1)$
$\prod_{\left\langle i,j\right\rangle\in D}E(i,j)A=I$, thus
$A^{-1}=\prod_{\left\langle i,j\right\rangle\in D}E_{\left\langle
i,j\right\rangle}(-1)\prod_{\left\langle i,j\right\rangle\in D}E(i,j)$, which
is a matching operator of which the division is $D$. By (iii), $A$ is also a
matching operator $\Box$.

###  4.2 Cooperation and matching equation

We give the following definitions.

######  Definition 7 (Cooperation)

Two matching operators $A,B$ are called cooperative if there is a new matching
operator $C$ so that $B=CA$. By Proposition 2 we have $A=C^{-1}B$, thus this
definition is symmetric for $A,B$.

######  Definition 8 (Cooperative set)

A set $\left\\{M_{1},\cdots,M_{m}\right\\}$ of $N$-order matching operators is
called a cooperative set if any two of these operators are cooperative. A
cooperative set $G=\left\\{I,M_{1},\cdots,M_{N-1}\right\\}$ is called complete
(for convenience, $I$ is also regarded as a “matching operator” but ignored).

######  Definition 9 (Path length)

For a row index $i$, we count the number of times $i$ was multiplied by $-1$
through its path in an operation $g$ (i.e., the mapping process of $i$), and
call the value of the number modulo $2$ the length of the path, denoted as
$len_{g}(i)$. A length is actually a Boolean value indicating whether $i$ is
multiplied by $-1$. e.g., let $g=BA$, then the path $i$ passes through in $g$
is $i\overset{\left\langle i,j\right\rangle_{A}\left\langle
j,k\right\rangle_{B}}{\mapsto}(-1)^{len_{g}(i)}k$. According to the definition
of a couple, $len_{g}(i)$ equals the XOR of all couples values on the path,
i.e., $len_{g}(i)=\left\langle i,j\right\rangle_{A}\oplus\left\langle
j,k\right\rangle_{B}$.

###### Remark 3

  * $($i$)$

Given two matching operators $A,B$, then from vector $a$, two vectors $Aa,Ba$
orthogonal with $a$ can be obtained. If $Aa\perp Ba$ as well, then these
vectors are pairwise orthogonal. By Proposition 1, this means that vector $Ba$
is generated by performing a matching operator $C$ to vector $Aa$, i.e.,
$B=CA$. That’s why to define cooperation.

  * $($ii$)$

Given $N$ $N$-dimensional column vectors
$\textbf{{s}}^{(0)},\textbf{{s}}^{(1)},\cdots,\textbf{{s}}^{(N-1)}$ which
constitute a special orthogonal matrix $S_{N}$. For the first vector
$\textbf{{s}}^{(0)}$, any other vector must be generated by performing a
matching operator to it: $\textbf{{s}}^{(i)}=M_{i}\textbf{{s}}^{(0)}$, where
$M_{i}$ is the matching operator of column $i$ to column $0$, and $M_{0}=I$.
Therefore, the set $G_{S_{N}}=\left\\{I,M_{1},\cdots,M_{N-1}\right\\}$ must be
a complete cooperative set. Regardless of $\textbf{{s}}^{(0)}$, the matrix $S$
must be a special orthogonal matrix if its set of matching operators is
cooperative.

We give the following condition of cooperation.

###### Proposition 3

The necessary and sufficient condition for matching operators $A,B$ is as
follows:

  * •

$D(A)$ can be divided into several $4$-tuples (e.g., $\left\langle
i,j\right\rangle\&\left\langle k,l\right\rangle\to\left\\{i,j,k,l\right\\}$,
shown in Definition 13);

  * •

Operation $B$ corresponds to a bijection between $2$-tuples in any $4$-tuples
(e.g., $\left\\{i,j\right\\}\leftrightarrow\left\\{k,l\right\\}$);

  * •

Let $g=BABA$, then for any row index $i$, $len_{g}(i)=1$.

The above proposition is symmetric to $A,B$, and the equation $len_{g}(i)=1$
is called a matching equation. To prove Proposition 3, the following lemmas
are required.

###### Lemma 3

$AB=-BA$ is a necessary and sufficient condition for the product $AB$ of anti-
symmetric matrices $A,B$ to be anti-symmetric.

Proof: If $AB=-BA$, then $(AB)^{T}=B^{T}A^{T}=BA=-AB$. Conversely, if
$(AB)^{T}=-AB$, then $AB=-(AB)^{T}=-B^{T}A^{T}=-BA$ $\Box$.

###### Lemma 4

The following properties of cooperation hold:

  * $($i$)$

The necessary and sufficient condition for matching operators $A,B$ to
cooperate is that the product $AB$ or $BA$ is a matching operator.

  * $($ii$)$

There are not any two similar couples (i.e., they have the same row indexes,
shown in Definition 15) between the divisions of matching operators $A,B$
which are cooperative.

  * $($iii$)$

There are nt any two similar couples in the divisions of any two matching
operators in a cooperative set.

Proof:

  * $($i$)$

By Proposition 2, if $BA$ is a matching operator, so is $AB$ because $AB=-BA$,
and vice versa. Therefore, we only need to prove in the case of $BA$ to be a
matching operator, and then we have $B=-(BA)A$, which means that there is a
matching operator $C=-BA$ so that $B=CA$, i.e., $A,B$ cooperate; Conversely,
let $A,B$ cooperate, then there is a matching operator $C$ so that $B=CA$.
Right multiply both sides of $B=CA$ by $A$ at the same time, then $BA=-C$,
i.e., $BA$ is a matching operator.

  * $($ii$)$

By (i), $AB$ is a matching operator, in which any element $(i,i)=0$ by
Proposition 2. If there were any two similar couples between $D(A),D(B)$,
e.g., $\left\langle i,j\right\rangle$, then there is a scattered point $(i,j)$
in $A$, $(j,i)$ in $B$, thus $(i,i)$ in $AB$, which causes a contradiction.

  * $($iii$)$

Obviously by (ii) and the definition of a cooperative set (see Definition 8)
$\Box$.

Now we can prove Proposition 3.

Proof of Proposition 3:

  * •

(Sufficiency) Without loss of generality, let $\left\langle
i,j\right\rangle_{A},\left\langle k,l\right\rangle_{A}\in D(A)$, $\left\langle
j,k\right\rangle_{B},\left\langle i,l\right\rangle_{B}\in D(B)$, and
$\left\\{i,j,k,l\right\\}$ be a $4$-tuple. Then for $i$, we can write down its
path in $g=BABA$ as

$i\overset{\left\langle i,j\right\rangle_{A}\left\langle
j,k\right\rangle_{B}\left\langle k,l\right\rangle_{A}\left\langle
l,i\right\rangle_{B}}{\mapsto}(-1)^{len_{g}(i)}i,$ (10)

thus

$len_{g}(i)=\left\langle i,j\right\rangle_{A}\oplus\left\langle
j,k\right\rangle_{B}\oplus\left\langle k,l\right\rangle_{A}\oplus\left\langle
l,i\right\rangle_{B}.$ (11)

And for $j$, its path is

$j\overset{\left\langle j,i\right\rangle_{A}\left\langle
i,l\right\rangle_{B}\left\langle l,k\right\rangle_{A}\left\langle
k,j\right\rangle_{B}}{\mapsto}(-1)^{len_{g}(j)}j.$ (12)

Note that

$\begin{aligned} &len_{g}(j)=\left\langle
j,i\right\rangle_{A}\oplus\left\langle i,l\right\rangle_{B}\oplus\left\langle
l,k\right\rangle_{A}\oplus\left\langle k,j\right\rangle_{B}\\\
&=\left(\left\langle i,j\right\rangle_{A}\oplus
1\right)\oplus\left(\left\langle j,k\right\rangle_{B}\oplus
1\right)\oplus\left(\left\langle k,l\right\rangle_{A}\oplus
1\right)\oplus\left(\left\langle l,i\right\rangle_{B}\oplus 1\right)\\\
&=\left\langle i,j\right\rangle_{A}\oplus\left\langle
j,k\right\rangle_{B}\oplus\left\langle k,l\right\rangle_{A}\oplus\left\langle
l,i\right\rangle_{B}\\\ &=len_{g}(i)\end{aligned},$ (13)

so we get $len_{g}(j)=len_{g}(i)=1$. Similarly, we have
$len_{g}(k)=len_{g}(l)=1$, i.e.,
$\left\\{i,j,k,l\right\\}\overset{g}{\mapsto}\left\\{-i,-j,-k,-l\right\\}$.
The above conclusions are valid for all $4$-tuples, which means for any row
$i$, $i\overset{g}{\mapsto}-i$, i.e., $BABA=-I$. By Lemma 2, $BA$ is a
scattered matrix, thus is a matching operator by Proposition 2, then $A,B$
cooperate by Lemma 4.

  * •

(Necessity) Without loss of generality, for any couple $\left\langle
j,k\right\rangle_{B}\in D(B)$, we know $\left\langle j,k\right\rangle\notin
D(A)$ by Lemma 4. Suppose that $\left\langle i,j\right\rangle_{A},\left\langle
k,l\right\rangle_{A}\in D(A)$ correspondingly, and then $\left\langle
u,i\right\rangle_{B}\in D(B)$, where $u$ is an undetermined index. We know
that $BA$ is a matching operator by Lemma 4, so we have $g=BABA=-I$ by
Proposition 2. Therefore, for any row index $i$, we have
$i\overset{g}{\mapsto}-i$, so $len_{g}(i)=1$. The specific path in $g$ is

$i\overset{\left\langle i,j\right\rangle_{A}\left\langle
j,k\right\rangle_{B}\left\langle k,l\right\rangle_{A}\left\langle
u,i\right\rangle_{B}}{\mapsto}(-1)^{len_{g}(i)}i,$ (14)

note that $u=l$ must hold, otherwise the path is not connected. Thus, we get a
$4$-tuple $\left\\{i,j,k,l\right\\}$, and $B$ is corresponding to a bijection
$\left\\{i,j\right\\}\leftrightarrow\left\\{k,l\right\\}$. The above
discussion applies to any couple in $D(B)$, so we can deduce the condition
$\Box$.

###  4.3 Algorithm to generate a special orthogonal matrix

Based on Proposition 3, we have the following proposition which allows us to
reduce Problem 2 to the problem of a solving linear equation system.

###### Proposition 4

Given an $N$-order semi-orthogonal matrix, the necessary and sufficient
condition for it to have any solution is that the matching equation system
combined from all matching equations about it has a solution.

Proof: It can be seen from the proof process of Proposition 3 that for any
$4$-tuple, the matching equations of the $4$ row indexes of it are equivalent
to each other, so one $4$-tuple only corresponds to one independent matching
equation. Therefore, there are $\frac{N}{4}$ independent matching equations
between any two $N$-order matching operators satisfying the bijective
condition in Proposition 3 (i.e., (a) and (b)), and the necessary and
sufficient condition for these two matching operators to cooperate is that the
equation system combined from these $\frac{N}{4}$ matching equations has a
solution. For a semi-orthogonal matrix, it must satisfy the bijective
condition similar to the proof of Proposition 3, so this proposition can be
proved $\Box$.

###### Remark 4

An $N$-order semi-orthogonal matrix corresponds to $N-1$ matching operators,
and there are $\frac{N}{4}$ independent matching equations between every two
matching operators, thus the above equation system has
$\frac{N}{4}\binom{N-1}{2}=\frac{(N-1)(N-2)N}{8}$ equations, and there are
$\frac{N(N-1)}{2}$ unknowns which is the total number of all couples.
Therefore, we can get an $R\times C$ augmented matrix $\overline{A}$, where
$R=\frac{(N-1)(N-2)N}{8}$ and $C=\frac{N(N-1)}{2}+1$.

We can use XOR Gaussian elimination to determine the existence of solutions of
an $N$-order semi-orthogonal matrix, to solve Problem 2. We have presented
Algorithm 1 (see Appendix 1 for details). The algorithm only solves Problem 2,
but because it is very simple to generate a semi-orthogonal matrix (as
described by Wei et al.[23]), it can be regarded as an almost complete
algorithm to generate a special orthogonal matrix. In addition, the algorithm
can also be used to determine the existence of solutions of a semi-orthogonal
matrix, which can be used in the following section.

Algorithm 1 Find a solution of an $N$-order semi-orthogonal matrix.

0: An $N$-order matrix $S$ where $N=2^{n}$ and $n>0$.

0: $S$ is semi-orthogonal and constructed by $U=[N]$.

1: Compute all divisions of matching operators of $S$ and store them in table
$T$.

2: Set an $R\times C$ zero Boolean matrix $\overline{A}$ as an augmented
matrix.

3: Input matching equations into $\overline{A}$ for every two matching
operators stored in $T$.

4: Use XOR Gaussian elimination on $\overline{A}$.

5: if $rank(\overline{A})=rank(A)$ then

6: Generate a special solution $X$ of the matching equation.

7: Generate a special orthogonal matrix corresponding to $S$ by $X$.

8: Return $TRUE$.

9: else

10: Return $FALSE$.

11: end if

We analyze the complexity of Algorithm 1 in Appendix 1-(3). The exact time and
space complexity of Algorithm 1 are $O(N^{9})$ and $O(N^{5})$ respectively.
Obviously, the algorithm is polynomial for $N$.

##  5 Infeasibility proof of constructing a special orthogonal matrix for the
DRSP of an arbitrary $n$-qubit state

In this section, we will prove the infeasibility of constructing a special
orthogonal matrix, i.e., the non-solvability of Problem 1. The main idea is to
prove that each semi-orthogonal matrices can be simplified into a unique form
(called ordered type), and then use Algorithm 1 to determine that the unique
form of order $16$ or larger has no solution. The proof is arranged as
follows: in Section 5.1, we define the semi-matching operator and semi-
cooperation and prove that an $N$-size semi-cooperative set of $N$-order semi-
matching operators is a group. In Section 5.2, we study $n$-bijections so-
called and prove that the generator set of a semi-cooperative group satisfies
a property about $n$-bijections. We prove that any mapping table of the
generator set of a semi-cooperative group can be ordered in Section 5.3, and
then in Section 5.4, we prove that any semi-orthogonal matrix can be
simplified into the ordered type based on it. In the end, we prove that for
$n>3$ the ordered type is non-solvable by using Algorithm 1, so as to prove
the infeasibility in Section 5.5.

###  5.1 Semi-matching operators and semi-cooperative group

For semi-orthogonal matrices, we only need to study its exchanging operation,
so we have the following definitions.

######  Definition 10 (Semi-matching operator)

Similar to Eq. (7), a semi-matching operator $M$ is as follows:

$M=\prod_{\left\langle i,j\right\rangle\in D(M)}E(i,j),$ (15)

which is the operator corresponding to an operation of pairwise row-
exchanging. Its couples such as $\left\langle i,j\right\rangle$ and division
$D(M)$ can also be defined similarly.

######  Definition 11 (Semi-cooperation)

Two semi-matching operators $A,B$ are called semi-cooperative if there is a
new semi-matching operator $C$ so that $B=CA$.

######  Definition 12 (Semi-cooperative set)

A set $\left\\{M_{1},\cdots,M_{m}\right\\}$ of $N$-order semi-matching
operators is called a semi-cooperative set if any two of these operators are
semi-cooperative. A semi-cooperative set
$G=\left\\{I,M_{1},\cdots,M_{N-1}\right\\}$ is called complete.

The following proposition is a magical property of a semi-cooperative set.

###### Proposition 5

A complete semi-cooperative set $G=\left\\{I,M_{1},\cdots,M_{N-1}\right\\}$ of
$N$-order operators is an Abel group under matrix multiplication.

To prove Proposition 5, we first need the following lemmas.

###### Lemma 5

The following properties of a semi-matching operator $M$ hold:

  * $($i$)$

(Self-reversibility) $M^{-1}=M$;

  * $($ii$)$

(Symmetry) $M^{T}=M$, and all elements on the main diagonal of $M$ are $0$;

  * $($iii$)$

A scattered matrix $M$ must be a semi-matching operator if of which all
elements on the main diagonal are $0$, and it’s self-reversible or symmetric.

  * $($iv$)$

The cooperation between semi-matching operators $A,B$ is equivalent to that
the product $AB$ or $BA$ is also a semi-matching operator, and to that
$AB=BA$.

  * $($v$)$

There are not any two similar couples between the divisions of two semi-
cooperative semi-matching operators $A,B$, and thus in the divisions of any
two operators in a semi-cooperative set.

  * $($vi$)$

The necessary and sufficient condition for semi-matching operators $A,B$ to
cooperate is that $D(A)$ can be divided into several $4$-tuples, and operation
$B$ corresponds to a bijection between $2$-tuples in any $4$-tuples.

Proof: Similar to Proposition 2, Proposition 3, Lemma 3 and Lemma 4 $\Box$.

###### Lemma 6

For a complete semi-cooperative set of $N$-order operators, $\forall 0\leq
i<N$, we denote $M^{(i)}$ as the operator satisfying $\left\langle
0,i\right\rangle\in D(M^{(i)})$. Then $\forall 0\leq i,j<N$, if $\left\langle
j,x\right\rangle\in D(M^{(i)})$, then $\left\langle i,x\right\rangle\in
D(M^{(j)})$.

Proof: Because $M^{(i)}$ semi-cooperate with $M^{(j)}$ and $\left\langle
0,i\right\rangle,\left\langle j,x\right\rangle\in D(M^{(i)})$, then
$\left\\{0,i,j,x\right\\}$ is a $4$-tuple and $M^{(j)}$ corresponds to a
bijection between $\left\langle 0,i\right\rangle,\left\langle
j,x\right\rangle$ by Lemma 5. By $\left\langle 0,j\right\rangle\in
D(M^{(j)})$, we have $\left\langle i,x\right\rangle\in D(M^{(j)})$ $\Box$.

###### Remark 5

By Lemma 5, there are not any two similar couples in $G$, thus all
$(N-1)\frac{N}{2}$ couples in $G$ traverse exactly all possible
$\binom{N}{2}=\frac{N(N-1)}{2}$ couples. Thus, $\forall 0\leq i<N$,
$\left\langle 0,i\right\rangle$ must exist in $G$, and for $i\neq i^{\prime}$,
$\left\langle 0,i\right\rangle$ and $\left\langle 0,i^{\prime}\right\rangle$
belong to different operators.

Now we can prove Proposition 5.

Proof of Proposition 5: Obviously the associativity, reversibility
($M^{-1}=M$), unit element existence ($I$), and commutativity ($AB=BA$ if they
semi-cooperate) of $G$ are all satisfied. For the closeness, we only need to
prove that for any two operators $M^{(a)},M^{(b)}\in G$, $M^{(b)}M^{(a)}\in G$
also holds, where $a,b$ is as specified in Lemma 6.

Assume $\left\langle b,c\right\rangle_{a}\in D(M^{(a)})$ and consider
$M^{(c)}\in G$. Because of the semi-cooperation between $M^{(a)},M^{(b)}$, we
can consider each $4$-tuple of them. Without loss of generality, assume
$\left\langle i,j\right\rangle_{a}\left\langle k,l\right\rangle_{a}\in
D(M^{(a)}),\left\langle i,k\right\rangle_{b}\left\langle
j,l\right\rangle_{b}\in D(M^{(b)})$, then $\left\langle
i,l\right\rangle_{ba}\left\langle j,k\right\rangle_{ba}\in D(M^{(b)}M^{(a)})$.
Consider $M^{(c)}$, then for $\left\langle i,j\right\rangle_{a}$, $M^{(c)}$
corresponds to a bijection from it to a new couple $\left\langle
x,y\right\rangle_{a}\in D(M^{(a)})$, and we assume $\left\langle
i,x\right\rangle_{c},\left\langle j,y\right\rangle_{c}\in D(M^{(c)})$.
Consider $M^{(i)}$, then we have $\left\langle
b,k\right\rangle_{i},\left\langle c,x\right\rangle_{i}\in D(M^{(i)})$ because
$\left\langle i,k\right\rangle_{b}\in D(M^{(b)}),\left\langle
i,x\right\rangle_{c}\in D(M^{(c)})$ by Lemma 6. Note that $M^{(i)}$ and
$M^{(a)}$ semi-cooperate and $\left\langle b,c\right\rangle_{a}\in
D(M^{(a)})$, then $M^{(i)}$ have a bijection $\left\langle
b,c\right\rangle_{a}\leftrightarrow\left\langle k,x\right\rangle_{a}$, which
means $x=l$ thus $y=k$. Therefore, $\left\langle
i,l\right\rangle_{c}\left\langle j,k\right\rangle_{c}\in D(M^{(c)})$, which is
the same as $M^{(b)}M^{(a)}$.

For each $4$-tuple, $M^{(c)}$ is the same as $M^{(b)}M^{(a)}$, thus
$M^{(b)}M^{(a)}=M^{(c)}\in G$. Consequently, the set is an Abel group $\Box$.

Considering the self-reversibility, as an Abel group of order $N=2^{n}$, a
semi-cooperative group $G$ of $N$-order semi-matching operators has $n$
independent generators $\left\\{M_{1},M_{2},\cdots,M_{n}\right\\}$, which form
a generator set $\hat{G}$ of size $n$. Proposition 5 indicates that if we have
a generator set of the group, then the group is determined. Thus, Problem 3
can be reduced to the following problem.

###### Problem 4

(Find all semi-cooperative generator sets) Given $N=2^{n}$, find all $n$-size
generator sets of $N$-order semi-matching operators.

###  5.2 Bijections and semi-cooperative generator set

Observe the following semi-orthogonal matrices:

$\left|\overline{S}_{4}\right|=\begin{pmatrix}a_{0}&a_{1}&a_{2}&a_{3}\\\
a_{1}&a_{0}&a_{3}&a_{2}\\\ a_{2}&a_{3}&a_{0}&a_{1}\\\
a_{3}&a_{2}&a_{1}&a_{0}\end{pmatrix},\left|\overline{S}_{8}\right|=\begin{pmatrix}a_{0}&a_{1}&a_{2}&a_{3}&a_{4}&a_{5}&a_{6}&a_{7}\\\
a_{1}&a_{0}&a_{3}&a_{2}&a_{5}&a_{4}&a_{7}&a_{6}\\\
a_{2}&a_{3}&a_{0}&a_{1}&a_{6}&a_{7}&a_{4}&a_{5}\\\
a_{3}&a_{2}&a_{1}&a_{0}&a_{7}&a_{6}&a_{5}&a_{4}\\\
a_{4}&a_{5}&a_{6}&a_{7}&a_{0}&a_{1}&a_{2}&a_{3}\\\
a_{5}&a_{4}&a_{7}&a_{6}&a_{1}&a_{0}&a_{3}&a_{2}\\\
a_{6}&a_{7}&a_{4}&a_{5}&a_{2}&a_{3}&a_{0}&a_{1}\\\
a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\end{pmatrix},$ (16)

note that compared to column $0$, column $1$ has row-exchanging:
$\\{0\\}\leftrightarrow\\{1\\},\\{2\\}\leftrightarrow\\{3\\},\cdots$; column
$2,3$ have row-exchanging:
$\\{0,1\\}\leftrightarrow\\{2,3\\},\\{4,5\\}\leftrightarrow\\{6,7\\}$; columns
$4,5,6,7$ have row-exchanging $\\{0,1,2,3\\}\leftrightarrow\\{4,5,6,7\\}$. The
above property is abstracted as follows: a semi-cooperative set
$\\{M_{1},M_{2},\cdots,M_{n}\\}$ of $N$-order semi-matching operators
satisfies:

  * •

$M_{1}$ has row-exchanging:
$\\{i\\}\leftrightarrow\\{j\\},\\{k\\}\leftrightarrow\\{l\\},\cdots$

  * •

$M_{2}$ has row-exchanging:
$\\{i,j\\}\leftrightarrow\\{k,l\\},\\{m,n\\}\leftrightarrow\\{o,p\\},\cdots$

  * •

$M_{3}$ has row-exchanging:
$\\{i,j,k,l\\}\leftrightarrow\\{m,n,o,p\\},\\{q,r,s,t\\}\leftrightarrow\\{u,v,w,x\\},\cdots$

  * •

$\cdots$

We will strictly describe and prove this property. Firstly, take any positive
integer power $n$ of $2$, where $1\leq n\leq N$, we have the following
definitions.

######  Definition 13 ($n$-tuple)

A set $\left\\{k_{1},k_{2},\cdots.k_{n}\right\\}$ of row (or column) indexes
is called an $n$-tuple, denoted as $T^{n}$, which is the promotion of a couple
or a $4$-tuple.

######  Definition 14 ($n$-bijection)

An $n$-bijection satisfies the following recursive definition:

  * •

A $1$-bijection $\sigma^{1}$ is a bijection between two $1$-tuples, i.e.,
$\sigma^{1}:T^{1}_{i}\leftrightarrow T^{1}_{j}$.

  * •

An $n$-bijection $\sigma^{n}$ is a bijection between two $n$-tuples:
$\sigma^{n}:\left(T^{\frac{n}{2}}_{i}+T^{\frac{n}{2}}_{j}\right)\leftrightarrow\left(T^{\frac{n}{2}}_{k}+T^{\frac{n}{2}}_{l}\right)$,
where “$+$” means taking the union set. We stipulate that
$\sigma^{n}=\left\\{T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{l},T^{\frac{n}{2}}_{j}\leftrightarrow
T^{\frac{n}{2}}_{k}\right\\}$ or $\left\\{T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{k},T^{\frac{n}{2}}_{j}\leftrightarrow
T^{\frac{n}{2}}_{l}\right\\}$, where $T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{l}$ and others are all $\frac{n}{2}$-bijections.

######  Definition 15 ($n$-similar)

Two $n$-bijections $\sigma^{n}_{i}:T^{n}_{i1}\leftrightarrow
T^{n}_{i2},\sigma^{n}_{j}:T^{n}_{j1}\leftrightarrow T^{n}_{j2}$ are called
similar, denoted as $\sigma^{n}_{i}\sim\sigma^{n}_{j}$, if their image and
preimage sets are the same respectively, i.e., $T^{n}_{i1}=T^{n}_{j1}$ and
$T^{n}_{i2}=T^{n}_{j2}$, and they are combined from the same
$\frac{n}{2}$-bijections. Two $N$-order semi-matching operators $A,B$ are
called $n$-similar, denoted as $A\overset{n}{\sim}B$, if each $n$-bijection
$\sigma^{n}_{i}$ of $A$ one-to-one corresponds to an $n$-bijection
$\sigma^{n}_{j}$ of $B$ so that $\sigma^{n}_{i}\sim\sigma^{n}_{j}$, and called
$n$-dissimilar if not, denoted as $A\overset{n}{\nsim}B$. $n$-similarity is
obviously an equivalence relation.

###### Remark 6

  * $($i$)$

Obviously, each $n$-bijection $\sigma^{n}$ can be written as
$\sigma^{n}=T^{n}_{i}\leftrightarrow T^{n}_{j}$, and even can be a self-
mapping, i.e., $T^{n}_{i}=T^{n}_{j}$.

  * $($ii$)$

Any $n$-bijection $\sigma^{n}=\left\\{T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{l},T^{\frac{n}{2}}_{j}\leftrightarrow
T^{\frac{n}{2}}_{k}\right\\}$ can be seen as a combination (i.e., product) of
two $\frac{n}{2}$-bijections:
$\sigma^{n}=\sigma^{\frac{n}{2}}_{1}\sigma^{\frac{n}{2}}_{2}$, where
$\sigma^{\frac{n}{2}}_{1}:T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{l},\sigma^{\frac{n}{2}}_{2}:T^{\frac{n}{2}}_{j}\leftrightarrow
T^{\frac{n}{2}}_{k}$.

  * $($iii$)$

For any $n$-bijection $\sigma^{n}=T^{n}_{i}\leftrightarrow T^{n}_{j}$ that is
not a self-mapping, there is only one $2n$-tuple $T^{2n}=T^{n}_{i}\cup
T^{n}_{j}$ corresponding to it. Without confusion, we can consider
$\sigma^{n}$ as $T^{2n}$, e.g., a couple is both a $1$-bijection and a
$2$-tuple. Let semi-matching operator $A$ has two $\frac{n}{2}$-bijections
$T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{k},T^{\frac{n}{2}}_{j}\leftrightarrow T^{\frac{n}{2}}_{l}$,
semi-matching operator $B$ has
$\left(T^{\frac{n}{2}}_{i}+T^{\frac{n}{2}}_{j}\right)\leftrightarrow\left(T^{\frac{n}{2}}_{k}+T^{\frac{n}{2}}_{l}\right)$,
then we say $B$ performs on an $n$-tuple
$\left(T^{\frac{n}{2}}_{i}+T^{\frac{n}{2}}_{j}\right)$ of $A$.

  * $($iv$)$

Similar $n$-bijections can be called of the same class. Any class of
$n$-bijection
$\sigma^{n}:\left(T^{\frac{n}{2}}_{i}+T^{\frac{n}{2}}_{j}\right)\leftrightarrow\left(T^{\frac{n}{2}}_{k}+T^{\frac{n}{2}}_{l}\right)$
corresponds to $2$ classes of specific $n$-bijection:
$\sigma^{n}_{1}=\left\\{T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{l},T^{\frac{n}{2}}_{j}\leftrightarrow
T^{\frac{n}{2}}_{k}\right\\}$ and
$\sigma^{n}_{2}\left\\{T^{\frac{n}{2}}_{i}\leftrightarrow
T^{\frac{n}{2}}_{k},T^{\frac{n}{2}}_{j}\leftrightarrow
T^{\frac{n}{2}}_{l}\right\\}$.

Now we give the following sufficient condition for the property proposed at
the beginning.

###### Proposition 6

The following properties about an $m$-size generator subset
$\\{M_{1},M_{2},\cdots,M_{m}\\}$ hold:

  * $($i$)$

In the subgroup $\left\langle M_{1},M_{2},\cdots,M_{m}\right\rangle$ generated
by $\\{M_{1},M_{2},\cdots,M_{m}\\}$, all operators are pairwise
$2^{m}$-similar.

  * $($ii$)$

$\forall 1\leq j<i\leq m$, $M_{i}$ performs on each $2^{j}$-tuple of $M_{j}$.

The above proposition means that a sufficient condition of the property at the
beginning of this section is that the set is a generator subset. To prove it,
we first need the following lemmas.

###### Lemma 7

The following properties of $n$-bijection hold:

  * $($i$)$

(Non-overlapping) In an $N$-order semi-matching operator, there are not any
two different overlapping $n$-bijection (i.e., their image or preimage sets
are the same);

  * $($ii$)$

(Boundedness) In a specific complete semi-cooperative set of $N$-order semi-
matching operators, the number of any class of $n$-bijections is $n$ at most.

Proof: We induct on $n$.

  * $($i$)$

If there are any two overlapping $n$-bijections, then at least one row index
is mapped into two indexes, which can not be by a matching operator.

  * $($ii$)$

    * $($a$)$

By Lemma 5, the number of any class of $1$-bijection is $1$ at most.

    * $($b$)$

Assume we have proved that the number of any class of $n$-bijection is $n$ at
most. For any class of $2n$-bijections
$\sigma^{2n}:\left(T^{n}_{i}+T^{n}_{j}\right)\leftrightarrow\left(T^{n}_{k}+T^{n}_{l}\right)$,
if it exists in the set, then it corresponds to $2$ classes of specific
$2n$-bijections: $\sigma^{2n}_{1}=\left\\{T^{n}_{i}\leftrightarrow
T^{n}_{l},T^{n}_{j}\leftrightarrow
T^{n}_{k}\right\\},\sigma^{2n}_{2}=\left\\{T^{n}_{i}\leftrightarrow
T^{n}_{k},T^{n}_{j}\leftrightarrow T^{n}_{l}\right\\}$, which are both
combined from $2$ classes of $n$-bijections. Each possibility of
$T^{n}_{i}\leftrightarrow T^{n}_{l}$ always exists with one possibility of
$T^{n}_{j}\leftrightarrow T^{n}_{k}$, thus if the number of
$T^{n}_{i}\leftrightarrow T^{n}_{l}$ is $n$, so is $T^{n}_{j}\leftrightarrow
T^{n}_{k}$. Therefore, the number of $\sigma^{2n}_{1}$ is at most $n$, and so
is $\sigma^{2n}_{2}$, so the number of $\sigma^{2n}$ is $2n$ at most (We are
not to traverse all theoretical possibilities of
$\sigma^{2n}_{1},\sigma^{2n}_{2}$, but consider in a specific complete semi-
cooperative set, in which the number is far less than the former).

The induction is completed $\Box$.

###### Lemma 8

Have two $N$-order semi-matching operators $A,B$, the following properties of
$n$-similarity hold:

  * $($i$)$

If $A\overset{n}{\sim}B$, then $A\overset{2n}{\sim}B$, and thus
$A\overset{n2^{k}}{\sim}B$ ($n2^{k}\leq N$, where $k$ is a positive integer).

  * $($ii$)$

If $A\overset{n}{\nsim}B$, then $A\overset{\frac{n}{2}}{\nsim}B$, and thus
$A\overset{n2^{-k}}{\nsim}B$ ($n2^{-k}\geq 1$, where $k$ is a positive
integer).

Proof:

  * $($i$)$

Each $2n$-bijection $\sigma^{2n}_{i}$ of $A$ can be written as a product of
two $n$-bijections $\sigma^{n}_{i1},\sigma^{n}_{i2}$, i.e.,
$\sigma^{2n}_{i}=\sigma^{n}_{i1}\sigma^{n}_{i2}$. Because
$A\overset{n}{\sim}B$, there are corresponding
$\sigma^{n}_{j1}\sim\sigma^{n}_{i1},\sigma^{n}_{j2}\sim\sigma^{n}_{i2}$ of
$B$. By Lemma 7, $\sigma^{n}_{j1},\sigma^{n}_{j2}$ don’t overlap, so
$\sigma^{2n}_{j}=\sigma^{n}_{j1}\sigma^{n}_{j2}\sim\sigma^{n}_{i1}\sigma^{n}_{i2}=\sigma^{2n}_{i}$,
i.e., $\sigma^{2n}_{j}$ is the $n$-bijection of $B$ similar to
$\sigma^{2n}_{i}$, thus $A\overset{2n}{\sim}B$. We can see
$A\overset{n2^{k}}{\sim}B$ by continuous recursion.

  * $($ii$)$

Similar to (i) $\Box$.

Now we can prove Proposition 6.

Proof of Proposition 6: We induct on $m$.

  * $($i$)$

Note that for any two semi-matching operators $A,B$, if assume $\left\langle
i,j\right\rangle_{A}\left\langle k,l\right\rangle_{A}\in D(A)$, $\left\langle
i,k\right\rangle_{B}\left\langle j,l\right\rangle_{B}\in D(B)$, then
$\left\langle i,l\right\rangle_{BA}\left\langle j,k\right\rangle_{BA}\in
D(BA)$. Thus $A,B,BA$ are pairwise $4$-similar.

    * $($a$)$

Obliviously, in $\left\langle M_{1}\right\rangle=\\{I,M_{1}\\}$ all operators
are pairwise $2^{1}=2$-similar.

    * $($b$)$

For $m>1$, Assume that we have proved that in $\left\langle
M_{1},M_{2},\cdots,M_{m}\right\rangle$ all operators are pairwise
$2^{m}$-similar, thus $2^{m+1}$-similar by Lemma 8. For $M_{m+1}$,
$\forall\overline{M}_{i}\in\left\langle
M_{1},M_{2},\cdots,M_{m}\right\rangle$, we have
$M_{m+1},\overline{M}_{i},M_{m+1}\overline{M}_{i}$ are pairwise $4$-similar,
thus $2^{m+1}$-similar. Note that $\left\langle
M_{1},M_{2},\cdots,M_{m},M_{m+1}\right\rangle=\left\langle
M_{1},M_{2},\cdots,M_{m}\right\rangle+\\{M_{m+1}\overline{M}_{i}|\overline{M}_{i}\in\left\langle
M_{1},M_{2},\cdots,M_{m}\right\rangle\\}$. Due to the transitivity of
similarity, the $2^{m+1}$-similarity holds for $\left\langle
M_{1},M_{2},\cdots,M_{m+1}\right\rangle$.

  * $($ii$)$

By (i), $\forall 1\leq j<i\leq m$, in $\left\langle
M_{1},M_{2},\cdots,M_{j-1}\right\rangle$ of which the order is $2^{j-1}$, all
operators are pairwise $2^{j-1}$-similar, thus all $2^{j-1}$ possibilities of
these $2^{j-1}$-bijections are traversed by Lemma 7. Therefore, any additional
generator $M_{i}$ is $2^{j-1}$-non-similar, thus $2^{j-2}$-non-similar to
them.

    * $($a$)$

Obliviously for $\forall 1\leq j<i\leq 1$.

    * $($b$)$

Assume that we have proved that $\forall 1\leq j<i\leq m$, $M_{i}$ performs on
each $2^{j}$-tuple of $M_{j}$. Consider $M_{m+1}$. For $j=1$ it is obvious by
Lemma 5. $\forall 1<j\leq m$, $M_{m+1}$ cooperates with $M_{j-1}$,
respectively, thus it performs on each $2^{j-1}$-tuple of $M_{j-1}$ as well as
$M_{j}$. By $M_{m+1}\overset{2^{j-1}}{\nsim}M_{j}$ and similar to the proof of
Proposition 6, without loss of generality, suppose that there are
$T^{2^{j-1}}_{1}\leftrightarrow_{j}T^{2^{j-1}}_{2},T^{2^{j-1}}_{3}\leftrightarrow_{j}T^{2^{j-1}}_{4}$
in $2^{j-1}$-bijections of $M_{j}$, and
$T^{2^{j-1}}_{1}\leftrightarrow_{m+1}T^{2^{j-1}}_{3},T^{2^{j-1}}_{2}\leftrightarrow_{m+1}T^{2^{j-1}}_{5}$
of $M_{m+1}$. Because $M_{m+1},M_{j}$ semi-cooperate, we have mapping
$T^{2^{j-1}}_{1}\overset{M_{m+1}M_{j}M_{m+1}M_{j}}{\to}T^{2^{j-1}}_{1}$, i.e.,
$T^{2^{j-1}}_{1}\leftrightarrow_{j}T^{2^{j-1}}_{2}\leftrightarrow_{m+1}T^{2^{j-1}}_{5}\leftrightarrow_{j}T^{2^{j-1}}_{3}\leftrightarrow_{m+1}T^{2^{j-1}}_{1}$,
leading to $T^{2^{j-1}}_{5}\leftrightarrow_{j}T^{2^{j-1}}_{3}$. However, there
is $T^{2^{j-1}}_{3}\leftrightarrow_{j}T^{2^{j-1}}_{4}$ of $M_{j}$, thus
$T^{2^{j-1}}_{5}=T^{2^{j-1}}_{4}$ must hold because of $2^{j-1}$-non-
overlapping by Lemma 7. Therefore, there is $2^{j}$-bijection
$\left(T^{2^{j-1}}_{1}+T^{2^{j-1}}_{2}\right)\leftrightarrow\left(T^{2^{j-1}}_{3}+T^{2^{j-1}}_{4}\right)$
of $M_{m+1}$, where $\left(T^{2^{j-1}}_{1}+T^{2^{j-1}}_{2}\right)$,
$\left(T^{2^{j-1}}_{3}+T^{2^{j-1}}_{4}\right)$ are $2^{j}$-tuples of $M_{j}$,
i.e., $M_{m+1}$ performs on each $2^{j}$-tuple of $M_{j}$. Now we know it
holds for $\forall 0\leq j<i\leq m+1$, so the induction is completed $\Box$.

###  5.3 Mapping table and its ordering

To describe how we order a semi-cooperative generator set, we first need the
following definitions.

######  Definition 16 (Mapping table)

For a generator set $\hat{G}=\left\\{M_{1},M_{2},\cdots,M_{n}\right\\}$, a
mapping table is a permutation of index sequence $[N]$ in which $\forall
M_{m}\in\hat{G}$, for each $2^{m}$-tuple of $M_{m}$, the two $2^{m-1}$-tuples
in it are adjacent. For each $2^{m}$-tuple $T^{2^{m}}$ in a mapping table, the
leftmost element $i$ of it is denoted as $i=left\left(T^{2^{m}}\right)$.

######  Definition 17 ($n$-order)

For a mapping table $T$ of a generator set
$\hat{G}=\left\\{M_{1},M_{2},\cdots,M_{n}\right\\}$, we have the following
recursive definition:

  * $($a$)$

$T$ is directly called $1$-ordered;

  * $($b$)$

If $T$ is $(m-1)$-ordered, and for each $2^{m-1}$-bijection
$\sigma:T^{2^{m-1}}_{1}\leftrightarrow T^{2^{m-1}}_{2}$of $M_{m}$,
$\sigma\left(left\left(T^{2^{m-1}}_{1}\right)\right)=left\left(T^{2^{m-1}}_{2}\right)$,
then $T$ is $m$-ordered.

Algorithm 2 Generate an $n$-ordered mapping table $T$ of a generator set
$\hat{G}=\left\\{M_{1},M_{2},\cdots,M_{n}\right\\}$ of $N=2^{n}$-order
operators.

0: A generator set $\hat{G}=\left\\{M_{1},M_{2},\cdots,M_{n}\right\\}$ of
$N=2^{n}$-order semi-matching operators and an $N$-size empty vector $T$.

1: $T\Leftarrow[N]$.

2: for $m\Leftarrow 1$ to $n$ do

3: for $2^{m}$-tuple $T_{x}^{2^{m}}=T_{x1}^{2^{m-1}}+T_{x2}^{2^{m-1}}$ of
$M_{m}$ do

4: Arrange $T_{x1}^{2^{m-1}}$ and $T_{x2}^{2^{m-1}}$ adjacent while
maintaining their internal arrangement.

5: end for

6: for $2^{m}$-tuple $T_{x}^{2^{m}}=T_{x1}^{2^{m-1}}+T_{x2}^{2^{m-1}}$ of
$M_{m}$ do

7: $i\Leftarrow left\left(T_{x1}^{2^{m-1}}\right)$.

8: $j\Leftarrow M_{m}(i)$.

9: if $j\neq left\left(T_{x2}^{2^{m-1}}\right)$ then

10: $k\Leftarrow 2^{m-1}$.

11: $R\Leftarrow T_{x2}^{2^{m-1}}$.

12: while $k>1$ do

13: $R=T^{\frac{k}{2}}_{1}+T^{\frac{k}{2}}_{2}$.

14: if $j\in T^{\frac{k}{2}}_{2}$ then

15: for $2^{k}$-tuple
$T^{k}_{y}=T^{\frac{k}{2}}_{y1}+T^{\frac{k}{2}}_{y2}\subseteq
T_{x2}^{2^{m-1}}$ do

16: Exchange $T^{\frac{k}{2}}_{y1}$ and $T^{\frac{k}{2}}_{y2}$ while
maintaining their internal arrangement.

17: end for

18: $k\Leftarrow\frac{k}{2}$.

19: $R\Leftarrow$ Current $T^{\frac{k}{2}}_{1}$.

20: end if

21: end while

22: end if

23: end for

24: end for

Algorithm 2 shows how to generate an $n$-ordered mapping table. We have the
following proposition.

###### Proposition 7

The outcome $T$ of Algorithm 2 must be an $n$-ordered mapping table of
$\hat{G}=\left\\{M_{1},M_{2},\cdots,M_{n}\right\\}$.

To prove it, we first need the following lemma.

###### Lemma 9

Have a mapping table $T$ of a generator set
$\hat{G}=\left\\{M_{1},M_{2},\cdots,M_{n}\right\\}$, then $\forall 1\leq m\leq
n$, if $T$ is $m$-ordered, then the couples of
$\left\\{M_{1},M_{2},\cdots,M_{m}\right\\}$ are determined.

Proof: We induct on $m$.

  * $($i$)$

Obviously, for $m=1$, the couples of $\left\\{M_{1}\right\\}$ are determined.

  * $($ii$)$

Assume that we have proved that for $1\leq m\leq n-1$, the couples of
$\left\\{M_{1},M_{2},\cdots,M_{m}\right\\}$ are determined. For $m+1$, we need
to prove that $M_{m+1}$ is determined. As a mapping table, $T$ tells us how
$M_{m+1}$ perform on $2^{m}$-tuples of $M_{m}$.

For each $2^{m+1}$-tuple $T^{2^{m+1}}=T^{2^{m}}_{1}+T^{2^{m}}_{2}$ of
$M_{m+1}$, we know
$M_{m+1}\left(left\left(T^{2^{m}}_{1}\right)\right)=left\left(T^{2^{m}}_{2}\right)$,
which determine a couple $\left\langle
left\left(T^{2^{m}}_{1}\right),left\left(T^{2^{m}}_{2}\right)\right\rangle$.
Let
$i=1,T^{1}_{1}=\left\\{left\left(T^{2^{m}}_{1}\right)\right\\},T^{1}_{2}=\left\\{left\left(T^{2^{m}}_{2}\right)\right\\},R^{2}=T^{1}_{1}+T^{1}_{2}$.
We perform the following recursive steps:

For $1\leq i\leq m$, we have
$R^{2^{i}}=T^{2^{i-1}}_{1}+T^{2^{i-1}}_{2},\left\langle
T^{2^{i-1}}_{1},T^{2^{i-1}}_{2}\right\rangle\in D(M_{m+1})$, where
$T^{2^{i-1}}_{1}\subseteq T^{2^{m}}_{1},T^{2^{i-1}}_{2}\subseteq
T^{2^{m}}_{2}$. Consider $M_{i}$, then we have $\left\langle
T^{2^{i-1}}_{1},M_{i}\left(T^{2^{i-1}}_{1}\right)\right\rangle,\left\langle
T^{2^{i-1}}_{2},M_{i}\left(T^{2^{i-1}}_{2}\right)\right\rangle\in D(M_{i})$.
By Proposition 6,
$\left(T^{2^{i-1}}_{1}+M_{i}\left(T^{2^{i-1}}_{1}\right)\right)$ and
$\left(T^{2^{i-1}}_{1}+M_{i}\left(T^{2^{i-1}}_{1}\right)\right)$ are both
$2^{i}$-tuples of $M_{i}$, thus
$T^{2^{i}}_{1}=\left(T^{2^{i-1}}_{1}+M_{i}\left(T^{2^{i-1}}_{1}\right)\right)\subseteq
T^{2^{m}}_{1}$,
$T^{2^{i}}_{2}=\left(T^{2^{i-1}}_{1}+M_{i}\left(T^{2^{i-1}}_{1}\right)\right)\subseteq
T^{2^{m}}_{2}$. Therefore,
$T^{2^{i-1}}_{1},M_{i}\left(T^{2^{i-1}}_{1}\right)$,
$T^{2^{i-1}}_{1},M_{i}\left(T^{2^{i-1}}_{1}\right)$ do not overlap. Because
$M_{m+1}$ performs on $2$-tuples of $M_{i}$, we have $\left\langle
T^{2^{i-1}}_{1},T^{2^{i-1}}_{1}\right\rangle,\left\langle
M_{i}\left(T^{2^{i-1}}_{1}\right),M_{i}\left(T^{2^{i-1}}_{1}\right)\right\rangle\in
D(M_{m+1})$, which include $2^{i}$ couples. Let
$R^{2^{i+1}}=T^{2^{i}}_{1}+T^{2^{i}}_{2}$, then $\left\langle
T^{2^{i}}_{1},T^{2^{i}}_{2}\right\rangle\in D(M_{m+1})$. Let $i=i+1$ and go to
the next step.

After the above steps, we have $2^{m}$ couples in $D(M_{m+1})$, which is all
the couples between $T^{2^{m}}_{1}$ and $T^{2^{m}}_{2}$. We do the above steps
for each $2^{m+1}$-tuple of $M_{m+1}$, then $M_{m+1}$ is determined, and so is
$\left\\{M_{1},M_{2},\cdots,M_{m},M_{m+1}\right\\}$.

The induction is completed $\Box$.

###### Remark 7

We point out that the above lemma only proves the uniqueness, and next we will
give a clear example as follows: denote the $i$-th element of $T$ ($0\leq
i\leq N-1$) as $t_{i}$, then $\forall 1\leq m\leq n$, each $2^{m-1}$-bijection
of $M_{m}$ is as
$\left\\{t_{a},t_{a+1},\cdots,t_{a+2^{m-1}-1}\right\\}\leftrightarrow\\{t_{a+2^{m-1}},t_{a+2^{m-1}+1},\cdots,t_{a+2^{m}-1}\\}$,
where $2^{m}|a$, and $\forall a\leq i\leq a+2^{m-1}-1$,
$M_{m}(t_{i})=t_{i+2^{m-1}}$.

Then, we can finally prove Proposition 7.

Proof of Proposition 7: In the algorithm, steps 3-5 make $T$ the mapping table
for $M_{m}$ which is correct obviously. Steps 6-23 make $T$ $n$-ordered, while
steps 10-21 make $j=left\left(T^{2^{m-1}}_{x2}\right)$. The key is to prove a
correspondence that for every two exchanged $2^{m-1}$-tuples
$T^{2^{m-1}}_{1},T^{2^{m-1}}_{2}$, the internal mappings are between the
corresponding positions, i.e., the ordinal numbers of every two elements
exchanged in the two $2^{m-1}$-tuples are the same.

  * $($i$)$

For $m=1$, $T$ is $1$-ordered, then between every two paired $1$-tuples, the
correspondence is obvious.

  * $($ii$)$

After processing $m$, assume that $\forall 1\leq l\leq m$, the correspondence
between every two paired $2^{l-1}$-tuples has been proved. Now process $m+1$.
After steps 3-5, for each $2^{m+1}$-tuple
$T_{x}^{2^{m+1}}=T_{x1}^{2^{m}}+T_{x2}^{2^{m}}$ of $M_{m+1}$, $T_{x1}^{2^{m}}$
and $T_{x2}^{2^{m}}$ are adjacent without change of the internal arrangement
of them thus without change of the correspondence. Now consider steps 10-21
which make $j=left\left(T^{2^{m}}_{x2}\right)$, especially steps 15-17. For
each time performing steps 15-17, we exchange $T^{\frac{k}{2}}_{y1}$ and
$T^{\frac{k}{2}}_{y2}$ as wholes for $1<k\leq 2^{m}$ and each $2^{k}$-tuple
$T^{k}_{y}=T^{\frac{k}{2}}_{y1}+T^{\frac{k}{2}}_{y2}\subseteq T_{x2}^{2^{m}}$,
and we will prove that $\forall 1\leq l\leq m$, it does not change the
previous correspondence. For $1\leq l<\log_{2}{k}$, it holds because exchanges
between $\frac{k}{2}$-tuples do not change the internal arrangement of
$2^{l-1}$-tuples where $2^{l-1}<\frac{k}{2}$; for $l=\log_{2}{k}$, it holds
because after any exchange between $\frac{k}{2}$-tuples without change of
their internal arrangement, the correspondence still exists; for
$\log_{2}{k}<l\leq m$, it still holds because the internal changes in all
$2^{l-1}$-tuple where $2^{l-1}\geq k$ is the same, thus the correspondence
remains. Therefore, after step 10-21, we have
$j=left\left(T^{2^{m}}_{x2}\right)$ and $M_{m+1}(i)=j$, i.e., $T$ is
$(m+1)$-ordered. As a necessary step of induction, it must be pointed out that
the correspondence for $l=m+1$ holds because when $T$ is $(m+1)$-ordered,
$M_{m+1}$ is determined by Lemma 9 and as described by Remark 7.

The induction is completed. As a result, $T$ is $n$-ordered after the whole
algorithm $\Box$.

###  5.4 Simplification of semi-orthogonal matrices

The following definition is the goal of our simplification.

######  Definition 18 (Ordered type)

Have an $N=2^{n}$-order semi-orthogonal matrix $\left|S_{N}\right|$ and it is
a complete semi-cooperative set
$G_{\left|S_{N}\right|}=\left\\{I,M_{1},M_{2},\cdots,M_{N-1}\right\\}$, where
$M_{i}$ corresponds to column $i$ of $\left|S_{N}\right|$.
$\left|S_{N}\right|$ is called an ordered type, if $\forall 1\leq i\leq
N-1,M_{i}=M^{(i)}$, and of the generator set
$\hat{G}_{\left|S_{N}\right|}=\left\\{M_{1},M_{2},\cdots,M_{2^{m-1}},\cdots,M_{2^{n-1}}\right\\}$,
the $n$-ordered mapping table $T=[N]$.

We will prove the following proposition, which is a solution to Problem 3.

###### Proposition 8

The following properties of ordered types hold:

  * $($i$)$

$\forall N=2^{n},n\geq 1$, have an $N$-dimensional column vector
$\textbf{{s}}^{(0)}$, then there is only one $N$-order ordered type denoted as
$\left|\overline{S}_{N}\right|$.

  * $($ii$)$

Any $N$-order semi-orthogonal matrix can be simplified into
$\left|\overline{S}_{N}\right|$.

  * $($iii$)$

In $\left|\overline{S}_{N}\right|$, $\forall 1\leq m\leq n$, each $2^{m}\times
2^{m}$ block in the upper left corner is semi-orthogonal.

To prove it, we should first prove the following lemma.

###### Lemma 10

The following properties of semi-orthogonal matrices $\left|S_{N}\right|$
hold:

  * $($i$)$

For the complete semi-cooperative set
$G_{\left|S_{N}\right|}=\left\\{I,M_{1},\cdots,M_{N-1}\right\\}$ of an
$N$-order semi-orthogonal matrix $\left|S_{N}\right|$, have an $N$-order row
permutation matrix $E$ corresponding to a permutation $\pi:[N]\to[N]$, then
the complete semi-cooperative set of $E\left|S_{N}\right|$ is
$G_{E\left|S_{N}\right|}=\left\\{I,EM_{1}E^{T},\cdots,EM_{N-1}E^{T}\right\\}$.

  * $($ii$)$

For any $N$-order semi-matching operator $M$, if $M(i)=j$, then
$\left(EME^{T}\right)(\pi(i))=\pi(j)$, i.e., if $\left\langle
i,j\right\rangle\in D(M)$, then $\left\langle\pi(i),\pi(j)\right\rangle\in
D\left(EME^{T}\right)$, where $E$ is as described above.

Proof:

  * $($i$)$

Assume the vector of column $0$ is $\textbf{{s}}^{(0)}$, then
$\left|S_{N}\right|=\left\\{\textbf{{s}}^{(0)},M_{1}\textbf{{s}}^{(0)},\cdots,M_{N-1}\textbf{{s}}^{(0)}\right\\}$,
thus

$\begin{aligned}
\left|S_{N}\right|&=\left\\{E\textbf{{s}}^{(0)},EM_{1}\textbf{{s}}^{(0)},\cdots,EM_{N-1}\textbf{{s}}^{(0)}\right\\}\\\
&=\left\\{E\textbf{{s}}^{(0)},EM_{1}E^{T}E\textbf{{s}}^{(0)},\cdots,EM_{N-1}E^{T}E\textbf{{s}}^{(0)}\right\\}\\\
&=\left\\{{\textbf{{s}}^{\prime}}^{(0)},EM_{1}E^{T}{\textbf{{s}}^{\prime}}^{(0)},\cdots,EM_{N-1}E^{T}{\textbf{{s}}^{\prime}}^{(0)}\right\\}\end{aligned},$
(17)

where ${\textbf{{s}}^{\prime}}^{(0)}=E\textbf{{s}}^{(0)}$.

  * $($ii$)$

A row-permutation matrix $E$ is the product of a series of row-exchanging
matrices, and $E^{T}$ corresponds to $\pi^{-1}$. Thus,
$\left(EME^{T}\right)(\pi(i))=\left(\pi
M\pi^{-1}\right)(\pi(i))=\pi(M(i))=\pi(j)$ $\Box$.

Then we can prove Proposition 8.

Proof of Proposition 8:

  * $($i$)$

As described in Remark 7, if the mapping table $T=[N]$, i.e., $\forall 0\leq
i\leq N-1,t_{i}=i$, then $\forall 1\leq m\leq n$, each $2^{m-1}$-bijection of
$M_{2^{m-1}}$ is as
$\left\\{a,a+1,\cdots,a+2^{m-1}-1\right\\}\leftrightarrow\left\\{a+2^{m-1},a+2^{m-1}+1,\cdots,a+2^{m}-1\right\\}$,
where $2^{m}|a$, and $\forall a\leq i\leq a+2^{m-1}-1$,
$M_{2^{m-1}}(i)=i+2^{m-1}$. Thus, the generator set
$\hat{G}_{\left|\overline{S}_{N}\right|}=\left\\{M_{1},M_{2},\cdots,M_{2^{m-1}},\cdots,M_{2^{n-1}}\right\\}$
is uniquely determined, and so is the group generated by it. Note that
$\forall 0\leq i\leq N-1,\left\langle 0,i\right\rangle_{i}\in D(M^{(i)})$,
thus all $M_{i}=M^{(i)}$ are also unique because so is the generator set, then
so is $\left|\overline{S}_{N}\right|$. As a clear example, we show
$\left|\overline{S}_{N}\right|$ as follows:

$\left|\overline{S}_{N}\right|=\begin{pmatrix}a_{0}&a_{1}&\cdots&a_{2^{n-1}-1}&a_{2^{n-1}}&a_{2^{n-1}+1}&\cdots&a_{2^{n}-2}&a_{2^{n}-1}\\\
a_{1}&a_{0}&\cdots&a_{2^{n-1}-2}&a_{2^{n-1}+1}&a_{2^{n-1}}&\cdots&a_{2^{n}-1}&a_{2^{n}-2}\\\
\vdots&\vdots&\ddots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\\
a_{2^{n-1}-1}&a_{2^{n-1}-2}&\vdots&a_{0}&a_{2^{n}-1}&a_{2^{n}-2}&\cdots&a_{2^{n-1}+1}&a_{2^{n-1}}\\\
a_{2^{n-1}}&a_{2^{n-1}+1}&\vdots&a_{2^{n}-1}&a_{0}&a_{1}&\cdots&a_{2^{n-1}-2}&a_{2^{n-1}-1}\\\
a_{2^{n-1}+1}&a_{2^{n-1}}&\vdots&a_{2^{n}-2}&a_{1}&a_{0}&\cdots&a_{2^{n-1}-1}&a_{2^{n-1}-2}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\cdots&\cdots\\\
a_{2^{n}-2}&a_{2^{n}-1}&\vdots&a_{2^{n-1}+1}&a_{2^{n-1}-2}&a_{2^{n-1}-1}&\vdots&a_{0}&a_{1}\\\
a_{2^{n}-1}&a_{2^{n}-2}&\vdots&a_{2^{n-1}}&a_{2^{n-1}-1}&a_{2^{n-1}-2}&\vdots&a_{1}&a_{0}\end{pmatrix},$
(18)

where
$\textbf{{s}}^{(0)}=\begin{pmatrix}a_{0},a_{1},\cdots,a_{N-1}\end{pmatrix}^{T}$.

  * $($ii$)$

For any $N$-order semi-orthogonal matrix $\left|S_{N}\right|$, we denote
$M_{i}=M^{(i)}$ and then we get a complete semi-cooperative set
$G_{\left|S_{N}\right|}=\left\\{I,M_{1},\cdots,M_{N-1}\right\\}$. We first
perform a column-permutation matrix $F$ on $\left|S_{N}\right|$ so that the
column order of $\left|S_{N}\right|F$ is the same as $G_{\left|S_{N}\right|}$.
Obviously $G_{\left|S_{N}\right|F}=G_{\left|S_{N}\right|}$. Then we consider
the generator set
$\hat{G}_{\left|S_{N}\right|F}=\left\\{M_{1},M_{2},\cdots,M_{2^{m-1}},\cdots,M_{2^{n-1}}\right\\}$
of $G_{\left|S_{N}\right|F}$, and use Algorithm 2 to generate an $n$-ordered
mapping table $T=\left\\{t_{i}|i=0,1,\cdots,N-1\right\\}$, where
$M_{m}(t_{i})=t_{j}$. Let $\pi:[N]\to[N]$ satisfies $\pi(t_{i})=i$, then we
get a corresponding row-permutation matrix $E$, and then
$\left(EM_{m}E^{T}\right)(\pi(t_{i}))=\pi(t_{j})$ by Lemma 10, i.e.,
$\left(EM_{m}E^{T}\right)(i)=j$. Thus for $E\left|S_{N}\right|F$, the new
mapping table $T^{\prime}=[N]$, i.e.,
$E\left|S_{N}\right|F=\left|\overline{S}_{N}\right|$.

  * $($iii$)$

It is easy to see from Eq. (18). To prove it, first by Proposition 6, $\forall
1\leq m\leq n$, in the generated subgroup $\left\langle
M_{1},M_{2},\cdots,M_{2^{m-1}}\right\rangle$, all operators are pairwise
$2^{m}$-similar. In the ordered type, each $2^{m}$-tuple is as
$\left\\{a,a+1,\cdots,a+2^{m}-1\right\\},2^{m}|a$. Note that $\left\langle
0,i\right\rangle_{i}\in D(M_{i})$ identifies which pairs of $2^{m}$-tuples are
bijectively mapped, i.e., $\forall 1\leq i\leq 2^{m}$, $M_{i}$ corresponds to
self-mapping of $2^{m}$-tuples, thus
$\left\\{I,M_{1},M_{2},\cdots,M_{2^{m}-2},M_{2^{m}-1}\right\\}=\left\langle
M_{1},M_{2},\cdots,M_{2^{m-1}}\right\rangle$. Therefore, the $2^{m}\times
2^{m}$ block $\left|\overline{S}_{2^{m}}\right|$ in the upper left corner is a
semi-orthogonal matrix with a subset
$V=\left\\{a_{0},a_{1},\cdots,a_{2^{m}-1}\right\\}\subseteq U$ $\Box$.

###  5.5 Infeasibility proof of construct a special orthogonal matrix

The feasibility of the simplification into the ordered type gives the
following proposition, which helps to solve Problem 1 thoroughly.

###### Proposition 9

The following two sentences are both necessary conditions for the existence of
solutions to Problem 1:

  * $($i$)$

The $N$-order ordered type $\left|\overline{S}_{N}\right|$ has a solution.

  * $($ii$)$

The $\frac{N}{2}$-order ordered type $\left|\overline{S}_{\frac{N}{2}}\right|$
has a solution.

Proof:

  * $($i$)$

By Proposition 8, Any $N$-order semi-orthogonal matrix can be simplified into
$\left|\overline{S}_{N}\right|$. For any $N$-order special orthogonal matrice
$S_{N}$, we have $\left|\overline{S}_{N}\right|=E\left|S_{N}\right|$ where $E$
is a row permutation matrix, and obviously
$\left|\overline{S}_{N}\right|=\left|ES_{N}\right|$. Thus if
$\left|S_{N}\right|$ has a solution $S_{N}$, then
$\left|\overline{S}_{N}\right|$ has a corresponding solution $ES_{N}$.

  * $($ii$)$

By Proposition 8, each $2^{m}\times 2^{m}$ block in the upper left corner of
$\left|\overline{S}_{N}\right|$ is semi-orthogonal, thus if
$\left|S_{N}\right|$ has a solution, then so do
$\left|\overline{S}_{N}\right|$ and $\left|\overline{S}_{\frac{N}{2}}\right|$
$\Box$.

In the case of $4$-qubit states, we need a $16$-order special orthogonal
matrix, so we have to consider $\left|S_{16}\right|$. We only consider the
case as $\textbf{{s}}^{(0)}=\begin{pmatrix}0,1,2,\cdots,15\end{pmatrix}^{T}$
because it’s more convenient and cooperative set is more important than the
values of elements. We determine the solution existence of
$\left|S_{16}\right|$ by Algorithm 1, and get a result of $FALSE$. On the
contrary, the results are both $TRUE$ for $\left|S_{4}\right|$ and
$\left|S_{8}\right|$. So we have the following theorem finally.

###### Theorem 1

$N$-order special orthogonal matrices exist when $N=2,4,8$ and don’t when
$N\geq 16$.

Therefore, it is proved that for $n>3$, it is infeasible to construct a
special orthogonal matrix for the DRSP of an arbitrary $n$-qubit state.

There are several similar RSP schemes that use some variant of the above
orthogonal matrices. For example, for the RSP of a general state, Xue et
al.[19] proposed to use matrix of which elements can have complex phases,
e.g.,

$\textbf{{s}}^{(i)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0i}}a_{\alpha_{0i}}e^{\imath\varphi_{i}}\\\
\left(-1\right)^{\sigma_{1i}}a_{\alpha_{1i}}e^{\imath\varphi_{i}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)i}}a_{\alpha_{(N-1)i}}e^{\imath\varphi_{i}}\end{pmatrix},$
(19)

where $\varphi_{i}$ are phases. However, at a glance, we will find that the
essence of this kind of matrices is similar to that of special orthogonal
matrices, and we can prove that the condition for them to exist is equivalent
to special orthogonal matrices (see Appendix 1 for details), so it’s also
infeasible for $n>3$.

##  6 Conclusion

In this paper, we present a polynomial-complexity algorithm to construct a
special orthogonal matrix for the DRSP of an arbitrary $n$-qubit state, and
prove that for $n>3$ such matrices do not exist. First, we split the
construction problem into two sub-problems, i.e., finding a solution of a
semi-orthogonal matrix and generating all semi-orthogonal matrices. Through
giving the definitions and properties of the matching operators, we prove that
the orthogonality of a special matrix is equivalent to the cooperation of
multiple matching operators, and then the construction problem is reduced to
the problem of solving an XOR linear equation system, which reduces the
construction complexity from exponential to polynomial level. We prove that
each semi-orthogonal matrix can be simplified into a unique ordered type, and
then use the proposed algorithm to confirm that the ordered type does not have
any solution when $n>3$. As a corollary, it is infeasible to construct such a
special matrix for the DRSP of an arbitrary $n$-qubit state. Considering that
DRSP is more valuable than probabilistic RSP, for an arbitrary number $n$ of
qubits, it may be more feasible to prepare a certain kind of state, such as an
equatorial state[7], GHZ state[18], cluster state[21], Brown-type state[22],
etc.

## Declarations

  * •

Conflict of interest The authors declare that they have no conflict of
interest.

  * •

Ethical statement Articles do not rely on clinical trials.

  * •

Human and animal participants All submitted manuscripts containing research
which does not involve human participants and/or animal experimentation.

## Data availability statement

Data sharing does not apply to this article as no datasets were generated or
analyzed during the current study.

Acknowledgements

This work is supported by the National Natural Science Foundation of China
(62071240), the Priority Academic Program Development of Jiangsu Higher
Education Institutions (PAPD), the Innovation Program for Quantum Science and
Technology (2021ZD0302902), the High Level Innovation Teams and Excellent
Scholars Program in Guangxi Institutions of Higher Education ([2019]52), and
the Special Funds for Local Science and Technology Development Guided by the
Central Government (ZY20198003).

References

## References

  * [1] H.K. Lo (2000), Classical-communication cost in distributed quantum-information processing: A generalization of quantum-communication complexity, Phys. Rev. A, 62(1), 012313.
  * [2] C.H. Bennett and D.P. DiVincenzo and P.W. Shor and J.A. Smolin and B.M. Terhal and W.K. Wootters (2001), Remote State Preparation, Phys. Rev. Lett., 87(7), 077902.
  * [3] D.W. Berry and B.C. Sanders (2003), Optimal Remote State Preperation, Phys. Rev. Lett., 90(5), 057901.
  * [4] C.H. Bennett and P. Hayden and D.W. Leung and P.W. Shor and A. Winter (2005), Remote preparation of quantum states, IEEE Trans. Inf. Theory, 51(1), 56–74.
  * [5] J.T. Barreiro and T.C. Wei and P.G. Kwiat (2010), Remote preparation of single-photon “hybrid” entangled and vector-polarization states, Phys. Rev. Lett., 105(3), 030407.
  * [6] C. Wang and Z. Zeng and X.H. Li (2015), Controlled remote state preparation via partially entangled quantum channel, Quantum Inf. Process., 14(3), 1077–1089.
  * [7] J. Shi (2021), Controlled cyclic remote state preparation of single-qutrit equatorial states, Mod. Phys. Lett., 36(33), 2150234.
  * [8] M.Y. Wang and Y.H. Zheng and L.X. Fu and F.L. Yan and T. Gao (2021), Remote preparation of a general single-photon hybrid state, Results Phys., 27, 104497.
  * [9] J.Y. Peng and Y. Xiang (2021), Bidirectional remote state preparation in noisy environment assisted by weak measurement, Opt. Commun., 499, 127285.
  * [10] A.G. Adepoju and B.J. Falaye and G.H. Sun and O. Camacho-Nieto and S.H. Dong (2017), Joint remote state preparation (JRSP) of two-qubit equatorial state in quantum noisy channels, Phys. Lett. A, 381(6), 581–587.
  * [11] S.Y. Sun and H.S. Zhang (2021), Double-direction quantum cyclic controlled remote state preparation of two-qubit states, Quantum Inf. Process., 20, 211.
  * [12] Y.J. Qian and Z.H. Xu and S.B. Xue and M. Jiang (2021), Effect of Quantum Noise on Deterministic Remote Preparation of an Arbitrary Two-Qubit State With a Relay Node, IEEE Access, 99, 1–1.
  * [13] X.Q. Xiao and J.M. Liu and G.H. Zeng (2011), Joint remote state preparation of arbitrary two- and three-qubit states, J. Phys. B: At. Mol. Opt., 44(9), 075501.
  * [14] Y.B. Zhan (2012), Deterministic remote preparation of arbitrary two- and three-qubit states, EPL, 98, 40005.
  * [15] Y.B. Zhan and P.C. Ma (2013), Deterministic joint remote preparation of arbitrary two- and three-qubit entangled states, Quantum Inf. Process., 12(2), 997–1009.
  * [16] Y.S. Ra and H.T. Lim and Y.H. Kim (2016), Remote preparation of three-photon entangled states via single-photon measurement, Phys. Rev. A, 94, 042329.
  * [17] X.B. Chen and Y.R. Sun and G. Xu and H.Y. Jia and Z.G. Qu and Y.X. Yang (2017), Controlled bidirectional remote preparation of three-qubit state, Quantum Inf. Process., 16(10), 244.
  * [18] H.Y. Dai and P.X. Chen and L.M. Liang and C.Z. Li (2006), Classical communication cost and remote preparation of the four-particle GHZ class state, Phys. Lett. A, 355, 285–288.
  * [19] Y. Xue and L. Shi and X.Y. Da and K.H. Zhou, and L.H. Ma and J.H. Wei and L.Q. Yu, and H. Hu (2019), Remote preparation of four-qubit states via two-qubit maximally entangled states, Quantum Inf. Process., 18(4), 103.
  * [20] Z.W. Sang (2020), Optimal Remote Preparation of a Four-qubit Entangled State Via a Ten-qubit Entangled State, Int. J. Theor. Phys., 59(8), 2480–2485.
  * [21] Z.L. Du and X.L. Li (2020), Deterministic joint remote state preparation of four-qubit cluster type with tripartite involvement, Quantum Inf. Process., 19(1), 39.
  * [22] H.B. Chen and H. Fu and X.W. Li and P.C. Ma and Y.B. Zhan (2016), Economic scheme for remote preparation of an arbitrary five-qubit Brown-type state, Pramana, 86(4), 783–-788.
  * [23] J.H. Wei and L. Shi and J.W. Luo and Y. Zhu and Q.Y. Kang and L.Q. Yu and H. Wu and J. Jiang and B.X. Zhao (2018), Optimal remote preparation of arbitrary multi-qubit real-parameter states via two-qubit entangled states, Quantum Inf. Process., 17(6), 141.
  * [24] S.X. Jiang and R.G. Zhou and R.Q. Xu and W.W. Hu and G.F. Luo (2019), Controlled joint remote preparation of an arbitrary N-qubit state, Quantum Inf. Process., 18(9), 265.
  * [25] K.H. Zhou, and L. Shi and B.B. Luo and Y. Xue and C. Huang and Z.Q. Ma and J.H. Wei (2019), Deterministic Controlled Remote State Preparation of Real-Parameter Multi-Qubit States via Maximal Slice States, Int. J. Theor. Phys., 58(12), 4079–4092.
  * [26] J.H. Wei and L. Shi and S.H. Zhao and K.H. Zhou and L.Q. Yu and W. Lu and L.H. Ma and B.X. Zhao (2019), Deterministic joint remote preparation of arbitrary multi-qubit states via three-qubit entangled states, Quantum Inf. Process., 18(8), 237.
  * [27] J.Y. Peng and M.Q. Bai and L. Tang and Z. Yang and Z.W. Mo (2021), Perfect controlled joint remote state preparation of arbitrary multi-qubit states independent of entanglement degree of the quantum channel, Quantum Inf. Process., 20, 340.
  * [28] J. Zhao (2022), Multi-party deterministic joint RSP of arbitrary multi-qubit states via maximal slice states, Mod. Phys. Lett. B, 36(5), 2150599.

Appendix A

In this appendix, the details of Algorithm 1 are shown. This appendix is
arranged as follows: we first introduce XOR Gaussian elimination, then present
the details of our algorithm, and last we analyze the complexity of the
algorithm.

(1) XOR Gaussian elimination

First, we introduce XOR linear equation system as follows, which is solved by
using XOR Gaussian elimination:

######  Definition A.1 (XOR linear equation system)

Have an unknown $n$-dimensional vector
$x=\begin{pmatrix}x_{0},x_{1},\cdots,x_{n-1}\end{pmatrix}^{T}$, a known
$m$-dimensional vector
$c=\begin{pmatrix}c_{0},c_{1},\cdots,c_{m-1}\end{pmatrix}^{T}$ and a known
$m\times n$ matrix $A=\begin{pmatrix}a_{00}&\cdots&a_{0(n-1)}\\\
\vdots&\ddots&\vdots\\\ a_{(m-1)0}&\cdots&a_{(m-1)(n-1)}\end{pmatrix}$, which
called Boolean where $\forall x_{i},c_{i},a_{ij}\in\\{0,1\\}$, then we have a
XOR linear equation system $Ax\equiv c\pmod{2}$, i.e.,

$\begin{pmatrix}a_{00}&\cdots&a_{0(n-1)}\\\ \vdots&\ddots&\vdots\\\
a_{(m-1)0}&\cdots&a_{(m-1)(n-1)}\end{pmatrix}\begin{pmatrix}x_{0}\\\ x_{1}\\\
\vdots\\\ x_{n-1}\end{pmatrix}\equiv\begin{pmatrix}c_{0}\\\ c_{1}\\\ \vdots\\\
c_{m-1}\end{pmatrix}\pmod{2},$ (A.1)

or

$\left\\{\begin{matrix}a_{00}x_{0}\oplus a_{01}x_{1}\oplus\cdots\oplus
a_{0(n-1)}x_{n-1}=c_{0}\\\ \vdots\\\ a_{(m-1)0}x_{0}\oplus
a_{(m-1)1}x_{1}\oplus\cdots\oplus
a_{(m-1)(n-1)}x_{n-1}=c_{(m-1)}\end{matrix}\right.,$ (A.2)

where “$\oplus$” means XOR.

######  Definition A.2 (Row-swap & Row-XOR))

To determine the existence of its solutions, we define the following
operations for any Boolean matrix:

  * $($i$)$

A Row-swap is that swaps rows $r_{i}$ and $r_{j}$, denoted as
$r_{i}\Leftrightarrow r_{j}$.

  * $($ii$)$

A Row-XOR is that XOR all elements in row $r_{j}$ to the corresponding
elements in row $r_{i}$, denoted as $r_{i}\oplus r_{j}$.

###### Lemma A.1

If an XOR equation system $A^{\prime}x\equiv c^{\prime}\pmod{2}$ is from
$Ax\equiv c\pmod{2}$ by a row-swap or row-XOR, then these two systems have the
same solutions.

Proof: Obviously for row-swap, so we only need to prove it for row-XOR. Have
an XOR equation system below

$\left\\{\begin{matrix}a_{00}x_{0}\oplus a_{01}x_{1}\oplus\cdots\oplus
a_{0(n-1)}x_{n-1}=c_{0}\\\ \vdots\\\ a_{i0}x_{0}\oplus
a_{i1}x_{1}\oplus\cdots\oplus a_{i(n-1)}x_{n-1}=c_{i}\\\ \vdots\\\
a_{j0}x_{0}\oplus a_{j1}x_{1}\oplus\cdots\oplus a_{j(n-1)}x_{n-1}=c_{j}\\\
\vdots\\\ a_{(m-1)0}x_{0}\oplus a_{(m-1)1}x_{1}\oplus\cdots\oplus
a_{(m-1)(n-1)}x_{n-1}=c_{(m-1)}\end{matrix}\right.,$ (A.3)

without loss of generality, assume a row-XOR $r_{i}\oplus r_{j}$, then we have

$\left\\{\begin{matrix}a_{00}x_{0}\oplus a_{01}x_{1}\oplus\cdots\oplus
a_{0(n-1)}x_{n-1}=c_{0}\\\ \vdots\\\ (a_{i0}\oplus
a_{j0})x_{0}\oplus(a_{i1}\oplus
a_{j1})x_{1}\oplus\cdots\oplus(a_{i(n-1)}\oplus a_{j(n-1)})x_{n-1}=c_{i}\\\
\vdots\\\ a_{j0}x_{0}\oplus a_{j1}x_{1}\oplus\cdots\oplus
a_{j(n-1)}x_{n-1}=c_{j}\\\ \vdots\\\ a_{(m-1)0}x_{0}\oplus
a_{(m-1)1}x_{1}\oplus\cdots\oplus
a_{(m-1)(n-1)}x_{n-1}=c_{(m-1)}\end{matrix}\right.$ (A.4)

from Eq. (A.3). Obviously, Eq. (A.3) and Eq. (A.4) have the same solutions if

$\left\\{\begin{matrix}a_{i0}x_{0}\oplus a_{i1}x_{1}\oplus\cdots\oplus
a_{i(n-1)}x_{n-1}=c_{i}\\\ a_{j0}x_{0}\oplus a_{j1}x_{1}\oplus\cdots\oplus
a_{j(n-1)}x_{n-1}=c_{j}\end{matrix}\right.$ (A.5)

and

$\left\\{\begin{matrix}(a_{i0}\oplus a_{j0})x_{0}\oplus(a_{i1}\oplus
a_{j1})x_{1}\oplus\cdots\oplus(a_{i(n-1)}\oplus a_{j(n-1)})x_{n-1}=c_{i}\\\
a_{j0}x_{0}\oplus a_{j1}x_{1}\oplus\cdots\oplus
a_{j(n-1)}x_{n-1}=c_{j}\end{matrix}\right.$ (A.6)

have the same solutions. Let
$x=\begin{pmatrix}x_{0},x_{1},\cdots,x_{n-1}\end{pmatrix}^{T}$ be a solution
of Eq. (A.3), i.e.,

$\left\\{\begin{matrix}a_{i0}x_{0}+a_{i1}x_{1}+\cdots+a_{i(n-1)}x_{n-1}=c_{i}+2k_{i}\\\
a_{j0}x_{0}+a_{j1}x_{1}+\cdots+a_{j(n-1)}x_{n-1}=c_{j}+2k_{j}\end{matrix}\right.$
(A.7)

where $k_{i},k_{j}$ are integer. Consequently, we have

$\begin{aligned} &(a_{i0}\oplus a_{j0})x_{0}\oplus(a_{i1}\oplus
a_{j1})x_{1}\oplus\cdots\oplus(a_{i(n-1)}\oplus a_{j(n-1)})x_{n-1}\\\
=&(a_{i0}+a_{j0}+2l_{0})x_{0}+(a_{i1}+a_{j1}+2l_{1})x_{1}+\cdots+(a_{i(n-1)}+a_{j(n-1)+2l_{n-1}})x_{n-1}\\\
&+2p\\\
=&(a_{i0}x_{0}+a_{i1}x_{1}+\cdots+a_{i(n-1)}x_{n-1})+(a_{j0}x_{0}+a_{j1}x_{1}+\cdots+a_{j(n-1)}x_{n-1})\\\
&+2(l_{0}+l_{1}+\cdots+l_{n-1}+p)\\\
=&c_{i}+2k_{i}+c_{j}+2k_{j}+2(l_{0}+l_{1}+\cdots+l_{n-1}+p)\\\
=&c_{i}+c_{j}+2(Integer)\\\ =&c_{i}\oplus c_{j}\end{aligned},$ (A.8)

where $l,p,k$ are all integer, i.e., any solution of Eq. (A.5) is also a
solution of Eq. (A.6), and vice versa because $a_{jq}\oplus(a_{iq}\oplus
a_{jq})=a_{iq}$. Therefore, Eq. (A.5) and Eq. (A.6) have the same solutions,
so do Eq. (A.3) and Eq. (A.4) $\Box$.

Therefore, the above two operations can be used to solve the equation system.
We transform the augmented matrix $\overline{A}=\left(A|c\right)$ of the
equation system into a row simplest matrix, and if
$rank(\overline{A})=rank(A)$, then the solution exists, otherwise not. If the
solution exists, then to get a special solution, for each row in eliminated
$\overline{A}$, we let all unconstrained variables (i.e., all variables
corresponding to non-zero elements except the first non-zero element) be $0$,
and let the constrained variable (i.e., the variable corresponding to the
first non-zero element) be the constant term, just like the ordinary Gaussian
elimination. Similar to the ordinary Gaussian elimination, the time and space
complexity of XOR Gaussian elimination are $O(\max^{3}(m,n))$ and $O(1)$
respectively.

(2) Algorithm details

In computer, the index of matrix element generally starts from $0$, and $i,j$
generally refer to row and column indexes respectively. We specify that
$U=[N]$ for convenience, and if we store any element as a $2$-tuple
$(a_{k},0)$ if it is $a_{k}\in U$ and $(a_{k},1)$ if it is $-a_{k}\in U$ so
that we can handle the case of $0$. For a semi-orthogonal matrix, we handle it
as a unfinished special orthogonal matrix of which the elements are all stored
as $(a_{k},1)$.

Each couple $\left\langle i,j\right\rangle,i<j$ is stored as a $3$-tuple
$\left(i,j,\left\langle i,j\right\rangle\right)$ (if $i>j$, we store it as
$\left(j,i,\left\langle j,i\right\rangle\right)$, where $\left\langle
j,i\right\rangle=\left\langle i,j\right\rangle\oplus 1$). We stipulate that if
in a couple the logical order and physical order of the two rows are opposite,
e.g., $\left\langle i,j\right\rangle$ is stored as $\left(j,i\left\langle
j,i\right\rangle\right)$, then set $c\oplus=1$ based on $\left\langle
i,j\right\rangle=\left\langle j,i\right\rangle\oplus 1$, where $c$ is the
constant term on the right side of a matching equation. The above stipulation
is because for any XOR equation $a_{0}x_{0}\oplus a_{1}x_{1}\oplus\cdots\oplus
a_{n-1}x_{n-1}=c$ for Boolean variables $x_{i}$ where $a_{i},c$ are all
Boolean constants, replace any $x_{i}$ with $(x_{i}\oplus 1)$ and then replace
$c$ with $c\oplus 1$, then the equation still holds. In addition, we treat
every couple in order, so the column index corresponding to each couple
$\left\langle x,y\right\rangle_{m}\in D(M_{m+1})$ is $m\times\frac{N}{2}+num$,
where $num$ is the serial number of $\left\langle x,y\right\rangle_{m}$ in
$D(M_{m+1})$.

We have Algorithm 3 for computing and storing all divisions of matching
operators of an $N$-order semi-orthogonal matrix $S$ in table $T$, Algorithm 4
for inputting matching equations into an $R\times C$ augmented matrix
$\overline{A}$ from table $T$, Algorithm 5 for solving the matching equation
system by XOR Gaussian elimination, and Algorithm 6 for generating a special
orthogonal matrix corresponding to $S$ by the solution output from Algorithm
5. Based on the above sub-algorithms, we can solve Problem 2 by using
Algorithm 1.

(3) Complexity analysis

In Algorithm 3, the hash method is used to speed up, thus its time and space
complexity are $O(N^{2}+N)=O(N^{2})$ and $O(N)$ respectively. In Algorithm 4,
$R=\frac{(N-1)(N-2)N}{8}$ equations are traversed and for each equation, four
queries are performed, where each query in the division of a matching operator
is of $O(N)$ time complexity, thus the time and space complexity of Algorithm
4 are $O(N^{4})$ and $O(1)$ respectively. For Algorithm 5, its time and space
complexity are
$O(\max^{3}(R,C))=O(R^{3})=O(\left[\frac{(N-1)(N-2)N}{8}\right]^{3})=O(N^{9})$
and $O(1)$ respectively as mentioned before. For Algorithm 6, obviously the
time and space complexity are $O(N^{2})$ and $O(1)$ respectively.
Consequently, considering the table $T$, the augmented matrix $\overline{A}$
and the solution vector $X$, the time and space complexity of Algorithm 1 are
$O(N^{2}+N^{4}+N^{9}+N^{2})=O(N^{9})$ and $O(N+1+1+R\times
C+(N-1)\times\frac{N}{2}+C-1)=O(N^{5})$ respectively.

Algorithm 3 Compute and store all divisions of matching operators of an
$N$-order semi-orthogonal matrix $S$.

0: An $N$-order matrix $S$ where $N=2^{n}$ and $n>0$, an empty
$(N-1)\times\frac{N}{2}$ matrix $T$ of couples $\left(i,j,\left\langle
i,j\right\rangle\right),i<j$, and an empty array $H$ of size $N$.

0: $S$ is semi-orthogonal and constructed by $U=[N]$.

1: for $i\Leftarrow 0$ to $N-1$ do

2: $H[S[i][1]]\Leftarrow i$.

3: end for

4: for $j\Leftarrow 1$ to $N-1$ do

5: for $i\Leftarrow 0$ to $N-1$ do

6: if $\nexists\left\langle i,m\right\rangle\in T[j-1]$ then

7: $t\Leftarrow H[S[i][j]]$.

8: if $S[t][j]=-S[i][0]$ then

9: Store $\left\langle i,t\right\rangle=1$ in $T[j-1]$.

10: else

11: Store $\left\langle i,t\right\rangle=0$ in $T[j-1]$.

12: end if

13: end if

14: end for

15: end for

Algorithm 4 Input matching equations into $\overline{A}$ for every two
matching operators stored in $T$ table $T$.

0: An $(N-1)\times\frac{N}{2}$ matrix $T$ of couples and an $R\times C$ zero
Boolean matrix $\overline{A}$ where
$R=\frac{(N-1)(N-2)N}{8},C=\frac{N(N-1)}{2}+1$.

0: $T$ has been filled by Algorithm 3.

1: $count\Leftarrow 0$.

2: for $0\leq a<b<N-1$ do

3: for $i\Leftarrow 0$ to $N-1$ do

4: if the $4$-tuple involved $i$ has not been traversed then

5: $c\Leftarrow 1$.

6: Query $\left\langle i,j\right\rangle$ in $T[a]$.

7: Query $\left\langle j,k\right\rangle$ in $T[b]$.

8: Query $\left\langle k,l\right\rangle$ in $T[a]$.

9: Query $\left\langle l,i\right\rangle$ in $T[b]$.

10: for $\left\langle x,y\right\rangle_{m}\in\left\\{\left\langle
i,j\right\rangle_{a},\left\langle j,k\right\rangle_{b},\left\langle
k,l\right\rangle_{a},\left\langle l,i\right\rangle_{b}\right\\}$ do

11: if $\left\langle x,y\right\rangle_{m}$ is stored as $\left(y,x\left\langle
y,x\right\rangle\right)$ in $T[m]$ then

12: $c\Leftarrow c\oplus 1$.

13: end if

14: end for

15: for $\left\langle x,y\right\rangle_{m}\in\left\\{\left\langle
i,j\right\rangle_{a},\left\langle j,k\right\rangle_{b},\left\langle
k,l\right\rangle_{a},\left\langle l,i\right\rangle_{b}\right\\}$ do

16: $num\Leftarrow$ the serial number of $\left\langle x,y\right\rangle_{m}$
in $T[m]$.

17: $\overline{A}[count][m\times\frac{N}{2}+num]\Leftarrow 1$.

18: end for

19: $\overline{A}[count][C-1]\Leftarrow c$.

20: $count\Leftarrow count+1$.

21: end if

22: end for

23: end for

Algorithm 5 Solve an $R\times C$ augmented matrix $\overline{A}$ by XOR
Gaussian elimination.

0: An $R\times C$ Boolean matrix $\overline{A}$ and an empty vector $X$ of
size $C-1$.

0: $\overline{A}$ has been filled by Algorithm 4.

1: $k\Leftarrow 0$.

2: for $j\Leftarrow 0$ to $C-1$ do

3: for $i\Leftarrow k$ to $R-1$ do

4: if $\overline{A}[i][j]\neq 0$ then

5: $r_{i}\Leftrightarrow r_{k}$.

6: for $i\Leftarrow k+1$ to $R-1$ do

7: if $\overline{A}[i][j]\neq 0$ then

8: $r_{i}\oplus r_{k}$.

9: end if

10: end for

11: $k\Leftarrow k+1$.

12: Break.

13: end if

14: if $k=R$ then

15: Break.

16: end if

17: end for

18: end for

19: for $i\Leftarrow k-1$ to $0$ do

20: for $j\Leftarrow 0$ to $C-1$ do

21: if $\overline{A}[i][j]\neq 0$ then

22: for $m\Leftarrow i-1$ to $0$ do

23: if $\overline{A}[m][j]\neq 0$ then

24: $r_{m}\oplus r_{i}$.

25: end if

26: end for

27: end if

28: end for

29: end for

30: if $\exists 0\leq j<C-1,\overline{A}[k-1][j]\neq 0$ then

31: Store a special solution in $X$.

32: Return $TRUE$.

33: else

34: Return $FALSE$.

35: end if

Algorithm 6 Generate a special orthogonal matrix corresponding to a $N$-order
semi-orthogonal matrix $S$.

0: An $N$-order matrix $S$ where $N=2^{n}$ and $n>0$, an
$(N-1)\times\frac{N}{2}$ matrix $T$ of couples, and a vector $X$ of size $C-1$
where $C=\frac{N(N-1)}{2}+1$.

0: $S$ is semi-orthogonal and constructed by $U=[N]$, $T$ has been filled by
Algorithm 3, and $X$ is a solution of the matching equation system of $S$ got
by Algorithm 5.

1: Value all couples in $T$ by $X$.

2: for $j\Leftarrow 1$ to $N-1$ do

3: for $\left\langle x,y\right\rangle\in T[j-1]$ do

4: $S[x][j]\Leftarrow(-1)^{\left\langle x,y\right\rangle\oplus 1}S[y][0]$.

5: $S[y][j]\Leftarrow(-1)^{\left\langle x,y\right\rangle}S[x][0]$.

6: end for

7: end for

Appendix B

As is mentioned, a generalization of Problem 1 is to construct an orthogonal
matrix of which the elements have complex phases, e.g.,

$\textbf{{s}}^{(i)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0i}}a_{\alpha_{0i}}e^{\imath\varphi_{i}}\\\
\left(-1\right)^{\sigma_{1i}}a_{\alpha_{1i}}e^{\imath\varphi_{i}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)i}}a_{\alpha_{(N-1)i}}e^{\imath\varphi_{i}}\end{pmatrix},$
(B.1)

where $\varphi_{i}$ are phases. We can prove that the condition for it to
exist is similar to the special orthogonal matrix.

###### Lemma B.1

Given two column vectors

$\begin{aligned}
\textbf{{s}}^{(i)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0i}}a_{\alpha_{0i}}e^{\imath\varphi_{i}}\\\
\left(-1\right)^{\sigma_{1i}}a_{\alpha_{1i}}e^{\imath\varphi_{i}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)i}}a_{\alpha_{(N-1)i}}e^{\imath\varphi_{i}}\end{pmatrix},\textbf{{s}}^{(j)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0j}}a_{\alpha_{0j}}e^{\imath\varphi_{j}}\\\
\left(-1\right)^{\sigma_{1j}}a_{\alpha_{1j}}e^{\imath\varphi_{j}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)j}}a_{\alpha_{(N-1)j}}e^{\imath\varphi_{j}}\end{pmatrix}\end{aligned},$
(B.2)

then the necessary and sufficient condition for
$\textbf{{s}}^{(i)}\perp\textbf{{s}}^{(j)}$ is that for two new vectors

$\begin{aligned}
\widetilde{\textbf{{s}}}^{(i)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0i}}a_{\alpha_{0i}}\\\
\left(-1\right)^{\sigma_{1i}}a_{\alpha_{1i}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)i}}a_{\alpha_{(N-1)i}}\end{pmatrix},\widetilde{\textbf{{s}}}^{(j)}=\begin{pmatrix}\left(-1\right)^{\sigma_{0j}}a_{\alpha_{0j}}\\\
\left(-1\right)^{\sigma_{1j}}a_{\alpha_{1j}}\\\ \vdots\\\
\left(-1\right)^{\sigma_{(N-1)j}}a_{\alpha_{(N-1)j}}\end{pmatrix}\end{aligned},$
(B.3)

we have $\widetilde{\textbf{{s}}}^{(i)}\perp\widetilde{\textbf{{s}}}^{(j)}$.

Proof:

$\begin{aligned}
\textbf{{s}}^{(i)\dagger}\textbf{{s}}^{(j)}&=\sum_{k=0}^{N-1}\left[(-1)^{\sigma_{ki}}a_{\alpha_{ki}}e^{-\imath\varphi_{i}}(-1)^{\sigma_{kj}}a_{\alpha_{kj}}e^{\imath\varphi_{j}}\right]\\\
&=\sum_{k=0}^{N-1}\left[(-1)^{\sigma_{ki}\oplus\sigma_{kj}}a_{\alpha_{ki}}a_{\alpha_{kj}}e^{\imath\left(-\varphi_{i}+\varphi_{j}\right)}\right]\\\
&=e^{\imath\left(-\varphi_{i}+\varphi_{j}\right)}\sum_{k=0}^{N-1}\left[(-1)^{\sigma_{ki}\oplus\sigma_{kj}}a_{\alpha_{ki}}a_{\alpha_{kj}}\right]\\\
&=e^{\imath\left(-\varphi_{i}+\varphi_{j}\right)}{\left[\widetilde{\textbf{{s}}}^{(i)\dagger}\widetilde{\textbf{{s}}}^{(j)}\right]}\end{aligned},$
(B.4)

thus obviously $\Box$.

By Lemma B.1, all the conclusions of the text can be applied here, therefore,
the generalized $N$-order special orthogonal matrix as above also exists when
$N=2,4,8$ and doesn’t when $N\leq 16$.