text:
\begin{document}
\title{Repeated Interaction Quantum Systems: Deterministic and Random}
\author{Alain Joye}
\address{Institut Fourier\\
Universit\'e de Grenoble\\ BP 74\\
38402 Saint Martin d'H\`eres, France}

\begin{abstract}
This paper gives an overview of recent results concerning the long time dynamics of repeated interaction quantum systems in a deterministic and random framework. We describe
the non equilibrium steady states (NESS) such systems display and we present, as a macroscopic consequence, a second law of thermodynamics these NESS give rise to. We also explain in some details the analysis of products of certain random matrices underlying  this dynamical problem.
\end{abstract}

\keywords{Non equilibrium quantum statistical mechanics, Repeated interaction quantum systems, Products of random matrices}

\bodymatter

\section{Introduction and  Model}

A repeated interaction quantum system consists of a reference quantum subsystem $\cS$ which interacts successively with the elements $\cE_m$ of a chain  $\cC=\cE_1+\cE_2+\cdots$ of independent quantum systems. At each moment in time, $\cS$ interacts precisely with one $\cE_m$ ($m$ increases as time does), while the other elements in the chain evolve freely according to their intrinsic dynamics. The complete evolution is described by the intrinsic dynamics of $\cS$ and of all the $\cE_m$, plus an interaction between $\cS$ and $\cE_m$, for each $m$. The latter is characterized by an interaction time $\tau_m>0$, and an interaction operator $V_m$ (acting on $\cS$ and $\cE_m$); during the time interval $[\tau_1+\cdots+\tau_{m-1}, \tau_1+\cdots+\tau_{m})$, $\cS$ is coupled to $\cE_m$ only via $V_m$.
Systems with this structure are important from a physical point of view, since they arise naturally as models for fundamental experiments on the interaction of matter with quantized radiation. As an example, the ``One atom maser'' provides an experimental setup in which the system $\cS$ represents a mode of the electromagnetic field, whereas the elements $\cE_k$ describe atoms injected in the cavity, one by one, which interact with the field during their flight in the cavity. After they leave the cavity, the atoms encode some properties of the field which can be measured on these atoms \cite{MWM} , \cite{WVHW}. For  repeated interaction systems  considered as {\it ideal}, i.e. such that all atoms are identical with identical interactions and times of flight through the cavity, corresponding mathematical analyses are provided in \cite{WBKM} , \cite{bjm}. To take into account the unavoidable fluctuations in the experiment setup used to study these repeated interaction systems, modelizations incorporating randomness have been proposed and studied in \cite{bjm2} and \cite{bjm3}. With a different perspective, repeated quantum interaction models also appear naturally in the mathematical study of modelization of open quantum systems by means of quantum noises, see \cite{AP} and references therein.
Any (continuous) master equation governing the dynamics of states on a
system $\cS$ can be viewed as the projection of a unitary evolution driving the system $\cS$ and a field of quantum noises in interaction.
It is shown in \cite{AP} how to recover
such continuous models as some delicate limit of a discretization given by a repeated quantum interaction model. Let us finally mention  \cite{pillet85} for results of a similar flavour in a somewhat different framework.

\medskip

Our goal is to  present the results of the papers  \cite{bjm} , \cite{bjm2} and \cite{bjm3} on (random) repeated interaction quantum systems, which focus on the long time behaviour of these systems.

\medskip

Let us describe the mathematical framework used to describe these quantum dynamical systems.
According to the fundamental principles of quantum mechanics, states
of the systems $\cS$ and $\cE_m$ are given by normalized vectors (or
density matrices) on Hilbert spaces $\cH_\cS$ and $\cH_{\cE_m}$,
respectively, \cite{AJP,BR}\footnote{A normalized vector $\psi$ defines a ``pure'' state $A\mapsto \scalprod{\psi}{A\psi}={\rm Tr}(\varrho_\psi A)$, where $\varrho_\psi=|\psi\rangle\langle\psi|$. A general ``mixed'' state is given by a density matrix $\varrho =\sum_{n\geq 1}p_n\varrho_{\psi_n}$, where the probabilities $p_n\geq 0$ sum up to one, and where the $\psi_n$ are normalized vectors.}. We assume that $\dim\cH_\cS<\infty$, while $\dim\cH_{\cE_m}$ may be infinite. Observables $A_\cS$ and $A_{\cE_m}$ of the systems $\cS$ and $\cE_m$ are bounded operators forming {\it
  von Neumann algebras} $\fm_\cS\subset \cB(\cH_\cS)$ and
$\fm_{\cE_m}\subset \cB(\cH_{\cE_m})$. They evolve according to the {\it Heisenberg
  dynamics} ${\mathbb R}\ni t\mapsto \alpha^t_\cS(A_\cS)$ and ${\mathbb
  R}\ni t\mapsto \alpha^t_{\cE_m}(A_{\cE_m})$, where
$\alpha^t_\cS$ and $\alpha^t_{\cE_m}$ are $*$-automorphism groups of
$\fm_\cS$ and $\fm_{\cE_m}$, respectively, see
e.g. \cite{BR}. We now introduce distinguished {\it reference states}, given by vectors $\psi_{\cS}\in\cH_\cS$ and $\psi_{\cE_m}\in \cH_{\cE_m}$. Typical choices for $\psi_\cS$, $\psi_{\cE_m}$ are equilibrium (KMS) states for the dynamics $\alpha^t_\cS$, $\alpha^t_{\cE_m}$, at inverse temperatures $\beta_\cS$, $\beta_{\cE_m}$. The Hilbert space of states of the total system is the tensor product
\[
\cH=\cH_\cS\otimes\cH_\cC,
\]
where $\cH_\cC=\bigotimes_{m\geq 1}\cH_{\cE_m}$, and where the infinite product is taken with respect to $\psi_\cC=\bigotimes_{m\geq 1}\psi_{\cE_m}$. The non-interacting dynamics is the product of the individual dynamics, defined on the algebra $\fm_{\cS}\bigotimes_{m\geq 1}\fm_{\cE_m}$ by $\alpha_\cs^t\bigotimes_{m\geq 1}\alpha_{\cE_m}^t$. It will prove  useful to consider the dynamics in the {\it Schr\"odinger picture}, i.e. as acting on vectors in $\cH$. To do this, we first implement the dynamics via unitaries, satisfying
\begin{equation}
\alpha_\#^t(A_\#) = \e^{\ri t L_\#} A_\# \e^{-\ri t L_\#},\ t\in{\mathbb R},\ \ \mbox{and $L_\#\psi_\#=0$},
\label{m1}
\end{equation}
for any $A_\#\in {\frak M}_\#$, where $\#$ stands for either $\cS$ or $\cE_m$. The self-adjoint operators $L_\cS$ and $L_{\cE_m}$, called {\it Liouville operators} or ``positive temperature Hamiltonians'', act on $\cH_\cS$ and $\cH_{\cE_m}$, respectively. The existence and uniqueness of $L_\#$ satisfying \fer{m1} is well known, under general assumptions on the reference states $\psi_\#$ \cite{BR}. We require these states to be {\it cyclic} and {\it separating}. In particular, \fer{m1} holds if the reference states are equilibrium states. Let $\tau_m>0$ and $V_m\in\fm_{\cS}\otimes\fm_{\cE_m}$ be the interaction time and interaction operator associated to $\cS$ and $\cE_m$. We define the (discrete) repeated interaction Schr\"odinger dynamics of a state vector $\phi\in\cH$, for $m\geq 0$, by
\begin{equation}
U(m)\phi = \e^{-\ri \widetilde L_m}\cdots\e^{-\ri \widetilde L_2}\e^{-\ri \widetilde L_1}\phi,
\label{m2}
\end{equation}
where
\begin{equation}
\widetilde L_k = \tau_k L_k+ \tau_k\sum_{n\neq k} L_{\cE_n}
\label{m3}
\end{equation}
describes the dynamics of the system during the time interval $[\tau_1+\cdots+\tau_{k-1},\tau_1+\cdots+\tau_k)$, which corresponds to the time-step $k$ of our discrete process. Hence $L_k$ is
\begin{equation}
L_k=L_\cS +L_{\cE_k} + V_k,
\label{m4}
\end{equation}
acting on $\cH_\cS\otimes\cH_{\cE_k}$. We understand that the operator $L_{\cE_n}$ in \fer{m3} acts nontrivially only on the $n$-th factor of the Hilbert space $\cH_\cC$ of the chain. As a general rule, we will ignore tensor products with the identity operator in the notation.

A state $\varrho(\cdot)={\rm Tr}(\rho\, \cdot\,)$ given by density matrix $\rho$ on $\cH$ is called a {\it normal state}.

Our goal is to understand the large-time asymptotics ($m\rightarrow \infty$) of expectations
\begin{equation}
\varrho\left(U(m)^* O U(m)\right)=\varrho(\alpha^m(O)),
\label{m5}
\end{equation}
for normal states $\varrho$ and certain classes of observables $O$ that we specify below. We denote the (random) repeated interaction dynamics by
\begin{equation}
\alpha^m(O) = U(m)^* O U(m).
\label{m5.1}
\end{equation}

\subsection{Van Hove Limit Type Results}

A first step towards understanding the dynamics of repeated interaction quantum systems  reduced to the reference system ${\cal S}$ was performed in the work \cite{aj}. This paper considers {\it Ideal Repeated Quantum Interaction Systems} which are characterized by identical elements ${\cal E}_k\equiv {\cal E}$ in the chain ${\cal C}$, constant interaction times $\tau_k\equiv \tau$  and identical interaction operators $V_k\equiv V\in  \fm_{\cS} \otimes  \fm_{\cE}  $ between  ${\cal S}$ and the elements  ${\cal E}$ of the chain.
In this setup, a Van Hove type analysis of the system is presented, in several regimes, to describe the dynamics of observables on $\cS$ in terms of a Markovian evolution equation of Lindblad type.  Informally,
the simplest result of \cite{aj} reads as follows. Assume the interaction operator
$V$ is replaced by $\lambda V$, where $\lambda>0$ is a coupling constant, and let $m$, the number of interactions during the
time $T=m\tau$, scale like $m\simeq t/\lambda^2$, where $0\leq t <\infty$ and $\tau$ are fixed. Assume all elements of the chain are in a same thermal state at temperature $\beta$.
Then, the weak coupling limit $\lambda\ra 0$ of the evolution of  any observable $O$  acting on $\cS$ obtained by tracing out the chain degrees of freedom from the evolution (\ref{m5.1}) satisfies, after removing a trivial free evolution, a continuous Lindblad type evolution equation in $t$. The temperature dependent generator is explicitely obtained from the interaction operator $V$ and the free dynamics. The asymptotic regimes of the parameters $(\lambda, \tau)$ characterized by $\tau\ra 0$ and $\tau\lambda^2\leq 1$ are also covered in \cite{aj}, giving rise to different Lindblad generators which all commute with the free Hamiltonian on $\cS$. The critical situation, where $\tau \ra 0$ with $\tau\lambda^2=1$  yields a quite general Lindblad generator, without any specific symmetry. In particular, it shows that any master equation driven by Lindblad operator, under reasonable assumptions, can
be viewed as a Van Hove type limit of a certain explicit repeated interaction quantum system.

\medskip
By contrast, the long time limit results obtained in  \cite{bjm} , \cite{bjm2} and \cite{bjm3} that we present here are obtained without  rescaling any coupling constant or parameter, as is usually the case with master equation techniques. It is possible to do without these approximations, making use of the structure of repeated interaction systems only, as we now show.

\section{Reduction to Products of Matrices}\label{sonly}

We first link the study of the dynamics to that of a product of reduced dynamics operators. In order to make the argument clearer, we only consider the expectation of an observable $A_\cS\in\fm_\cS$, and we take the initial state of the entire system to be given by the vector \begin{equation}
\psi_0=\psi_\cS\otimes\psi_\cC,
\label{m0}
\end{equation}
where the $\psi_\cS$ and $\psi_\cC$ are the reference states introduced above.
We'll comment on the general case below. The expectation of $A_\cS$ at the time-step $m$ is
\begin{equation}
\scalprod{\psi_0}{\alpha^m(A_\cS)\psi_0} = \scalprod{\psi_0}{P\e^{\ri\widetilde L_1}\cdots \e^{\ri\widetilde L_m}A_\cS\, \e^{-\ri\widetilde L_m}\cdots \e^{-\ri\widetilde L_1}P\psi_0},
\label{m6}
\end{equation}
where we introduced
\begin{equation}
P=\bbbone_{\cH_\cS}\bigotimes_{m\geq 1} P_{\psi_{\cE_m}},
\label{m7}
\end{equation}
the orthogonal projection onto $\cH_\cS\otimes {\mathbb C} \psi_\cC$.
A first important ingredient in our analysis is the use of {\it $C$-Liouvilleans} introduced in  \cite{jp2002} ,
which are operators $K_k$ defined by the properties
\begin{eqnarray}
\e^{\ri\widetilde L_k} A \e^{-\ri\widetilde L_k} &=&\e^{\ri K_k} A \e^{-\ri K_k},\label{m8}\\
K_k\,\psi_\cS\otimes \psi_\cC&=&0, \label{m8.1}
\end{eqnarray}
where $A$ in \fer{m8} is any observable of the total system. The identity \fer{m8} means that the operators $K_k$ implement the same dynamics as the $\widetilde L_k$ whereas relation \fer{m8.1} selects a unique generator of the dynamics among all operators which satisfy \fer{m8}. The existence of operators $K_k$ satisfying \fer{m8} and \fer{m8.1} is rooted to the Tomita-Takesaki theory of von Neumann algebras, c.f. \cite{jp2002} and references therein. It turns out that the $K_k$ are non-normal operators on $\cH$, while the $\widetilde L_k$ are self-adjoint. Combining \fer{m8} with \fer{m6} we can write
\begin{equation}
\scalprod{\psi_0}{\alpha^m(A_\cS)\psi_0} = \scalprod{\psi_0}{P\e^{\ri K_1}\cdots\e^{\ri K_m} P A_\cS\,\psi_0}.
\label{m9}
\end{equation}
A  second important ingredient of our approach is to realize that the {\it independence} of the sub-systems $\cE_m$ implies the relation
\begin{equation}
P\e^{\ri K_1}\cdots\e^{\ri K_m} P = P\e^{\ri K_1}P \cdots P\e^{\ri K_m}P.
\label{m10}
\end{equation}  Identifying $P\e^{\ri K_k}P$ with an operator $M_k$ on $\cH_\cS$, we thus obtain from \fer{m9} and \fer{m10},
\begin{equation}
\scalprod{\psi_0}{\alpha^m(A_\cS)\psi_0} = \scalprod{\psi_\cS}{M_1\cdots M_m A_\cS\, \psi_\cS}.
\label{m11}
\end{equation}
It follows from \fer{m8.1}
that $M_k\psi_\cS=\psi_\cS$, for all $k$, and,
because the operators $M_k=P\e^{\ri K_k}P$ implement a unitary dynamics, we
show (Lemma \ref{contraction}) that the $M_k$ are always contractions for some
suitable norm $|||\cdot |||$ on ${\mathbb C}^d$. This motivates the following\vspace{.0cm}\\

\noindent{\bf Definition:} Given a vector $\psi_\cS\in {\mathbb C}^d $ and a norm on
$|||\cdot |||$ on ${\mathbb C}^d$,  we call {\it Reduced Dynamics Operator} any
matrix which is a contraction for $|||\cdot |||$ and  leaves $\psi_\cS$ invariant.\vspace{.2cm}

\noindent{\it Remark:} In case all couplings between $\cS$ and $\cE_k$ are absent, $V_k\equiv0$,
$M_k=e^{i\tau_k L_\cS}$ is unitary and admits 1 as a degenerate eigenvalue.\\

We will come back on the properties of reduced dynamics operators (RDO's, for short) below. Let us emphasize here that the reduction process to product of RDO's is free from any approximation, so that the set of matrices $\{M_k=P\e^{\ri K_k}P\}_{k\in \mathbb N}$ encodes the complete dynamics. In particular, we show, using the cyclicity and separability of the reference vectors $\psi_\cS, \psi_{\cE_{k}}$, that the evolution of any normal state, not only $\bra \psi_0 , \ \cdot \ \psi_0\ket$, can be understood completely in terms of the product of these RDO's.

We are now in a position to state our main results concerning the asymptotic dynamics of normal states $\varrho$ acting on certain observables $O$. These result involve a spectral hypothesis which we introduce in the next \\

\noindent{\bf Definition:}
Let $\cme$ denote the set of reduced dynamics operators whose spectrum $\sigma(M)$
satisfies $\sigma(M)\cap \{z \in {\mathbb C} \ |\ |z|=1\}=\{1\}$ and $1$ is  simple eigenvalue.
\vspace{.2cm}

We shall denote by $P_{1,M}$ the spectral projector of a matrix $M$ corresponding to the eigenvalue 1. As usual, if the eigenvalue 1 is simple, with corresponding normalized eigenvector $\psi_\cS$, we shall write $P_{1,M}=|\psi_\cS\ket\bra\psi |$ for some
$\psi$ s.t. $\bra\psi|\psi_\cS\ket=1$.

\section{Results}

\subsection{Ideal Repeated Interaction Quantum System }

We consider first the case of {\em Ideal Repeated Interaction Quantum Systems}, characterized by
\bea
\cE_{k}&=&\cE, \ L_{\cE_{k}}=L_{\cE}, \  V_k=V, \ \tau_k=\tau \ \ \ \ \mbox{for all} \ \ k\geq 1,\nonumber \\
M_k&=& M, \  \ \forall k\geq 1.
\eea
\begin{thm}

\label{thm0}
{}\ Let $\alpha^{n}$ be the repeated interaction dynamics determined by one {\em RDO}
$M$. Suppose that $M\in\cme$ so that  $P_{1,M}=|\psi_\cS\ket\bra\psi |$. Then, for any
 $0<\gamma<\inf_{z\in \sigma(M)\setminus\{1\}}(1-|z|)$,
any  normal state $\varrho$, and any $A_\cs\in\fm_\cS$,
\begin{equation}
\varrho\left( \alpha^{n}(A_\cS)\right)=\scalprod{\psi}{A_\cS \psi_\cS}+
O(e^{-\gamma n}).
\label{m22}
\end{equation}
\end{thm}

\noindent{\it Remarks:} 1. The asymptotic state $\bra \psi | \cdot \psi_\cS\ket$ and
the exponential decay rate $\gamma$ are both determined by the spectral properties of
the RDO $M$.

2. On concrete examples, the verification of the spectral assumption on $M$ can be
done by rigorous perturbation theory, see \cite{bjm}. It is reminiscent of a Fermi Golden Rule type condition on the efficiency of the coupling $V$, see the remark  following the
definiton of RDO's.

3. Other properties  of ideal repeated interaction quantum systems are discussed in \cite{bjm} , e.g. continuous time evolution and correlations.\\

For deterministic systems which are {\it not} ideal, the quantity $ \varrho\left( \alpha^{n}(A_\cS)\right)$ keeps fluctuating as $n$ increases, which,  in general, forbids convergence, see Proposition \ref{limpsi}. That's why we resort to ergodic limits in a random setup, as we now explain.

\subsection{Random Repeated Interaction Quantum System}\label{rsetup}

To allow a description of the effects of fluctuations on the dynamics of repeated interaction quantum systems, we consider the following setup.

Let $\omega\mapsto M(\omega)$ be a random matrix valued variable on ${\mathbb C}^d$ defined on
a probability space $(\Omega,\cF,\p)$. We say that $M(\omega)$ is a {\it random reduced dynamics operator} (RRDO) if
\begin{itemize}
\item[(i)] There exists a norm $||| \cdot |||$ on $\C^d$ such that, for all $\omega$,
      $M(\omega)$ is a contraction on $\C^d$ for the norm $|||\cdot|||$.
\item[(ii)] There exists a vector $\psi_\cS$, constant in $\omega$, such that $M(\omega)\psi_\cS=\psi_\cS$, for all $\omega$.
\end{itemize}

To an RRDO $\omega \mapsto M(\omega)$ on $\Omega$ is naturally associated a iid {\it random reduced dynamics process} (RRDP)
\be\label{rrr}
 \po\mapsto M(\omega_1)\cdots M(\omega_n),\qquad \po\in{\Omega}^{{\mathbb N}^*},
\ee
where we define in a standard fashion a probability measure $\d\P$  on $\Omega^{\N^*}$ by
\[
\d\P =\Pi_{j\geq 1}\d \p_j, \ \ \ \mbox{where }
\ \ \ \d \p_j\equiv \d \p, \ \  \forall j\in \N^*.
\]
We shall write the expectation of any random variable $f$ as ${\mathbb E}[f]$.\\

Let us denote by $\alpha_{\po}^{n}$, $\po\in\Omega^{{\mathbb N}^*}$, the process obtained from \fer{m5.1}, \fer{m11}, where the $M_j=M(\omega_j)$ in \fer{m11} are iid random matrices. We call $\alpha_{\po}^{n}$ the random repeated interaction dynamics determined by the RRDO $M(\omega)=P\e^{\ri K(\omega)}P$. It is the independence of the successive elements $\cE_k$ of the chain $\cC$ which motivates the assumption that the process (\ref{rrr}) be iid.

\begin{thm}

\label{thm4}
{}\ Let $\alpha_{\po}^{n}$ be the random repeated interaction dynamics determined by an RRDO $M(\omega)$. Suppose that $\p(M(\omega)\in\cme)>0$. Then there exists a set $\overline{\Omega}\subset \Omega^{\N^*}$, s.t.  ${\mathbb P}(\overline{\Omega})=1$, and s.t. for any $\po\in\overline{\Omega}$, any normal state $\varrho$ and any $A_\cs\in\fm_\cS$,
\begin{equation}
\lim_{N\rightarrow\infty} \frac 1N\sum_{n=1}^N \varrho\left( \alpha^{n}_{\po}(A_\cS)\right)=\scalprod{\theta}{A_\cS \psi_\cS},
\label{m222}
\end{equation}
where $\theta=P_{1,{\mathbb E}[M]}^*\psi_\cS$.
\end{thm}

\medskip
\noindent {\it Remarks:} 1. Our setup allows us to treat systems having various sources of randomness. For example, random interactions or times of interactions, as well as  random characteristics of the systems $\cE_m$ and $\cS$ such as random temperatures and dimensions of the $\cE_m$ and of $\cS$.

2. The asymptotic state $\scalprod{\theta}{\ \cdot \ \psi_\cS} $ is again determined by
the spectral data of a matrix, the expectation ${\mathbb E}[M]$ of the RRDO $M(\omega)$. Actually, our hypotheses imply that ${\mathbb E}[M]$ belongs to $\cme$, see below.

3. The explicit computation of the asymptotic state, in this Theorem and in the previous one, is in general difficult. Nevertheless, they can be reached by rigorous perturbation theory, see the examples in \cite{bjm} , \cite{bjm2} and  \cite{bjm3}.

\subsection{Instantaneous Observables}

There are important physical observables  that describe exchange processes between $\cS$ and the chain $\cC$ and, which, therefore, are not represented by operators that act just on $\cS$. To take into account such phenomena, we consider the set of observables defined as follows.\vspace{.2cm}\\

\noindent{\bf Definition:} The
{\it instantaneous observables} of $\cS+\cC$ are of the form
\begin{equation}
O= A_\cS\otimes_{j=-l}^rB_m^{(j)},
\label{intro0'}
\end{equation}
where $A_\cS\in\fm_\cS$ and $B_m^{(j)} \in \fm_{\cE_{m+j}}$. \\

\noindent Instantaneous observables can be viewed as a train of $l+r+1$ observables, roughly centered at $\cE_m$, which travel along the chain $\cC$ with time.\\

Following the same steps as in Section \ref{sonly}, we arrive at the
following expression for the evolution of the state $\psi_0$ acting on an instantaneous observable $O$ at time $m$:
\begin{equation}
\scalprod{\psi_0}{\alpha^m(O)\psi_0} = \scalprod{\psi_0}{PM_1 \cdots M_{m-l-1} N_m(O)P\psi_0}.
\label{intro1'}
\end{equation}
Here again, $P$ is the orthogonal projection onto $\cH_\cS$, along $\psi_\cC$.
The operator $N_m(O)$ acts on $\cH_\cS$ and has the expression (Proposition 2.4 in \cite{bjm3})
\bea
&&N_m(O)\psi_0 = \\\nonumber
& &\hspace{.4cm}P \e^{\ri\tau_{m-l} \widetilde L_{m-l}}\cdots
\e^{\ri \tau_m \widetilde L_m} (A_\cS\otimes_{j=-l}^{r} B^{(j)}_m)
\e^{-\ri\tau_m \widetilde L_m}\cdots \e^{-\ri \tau_{m-l}
\widetilde L_{m-l}} \psi_0.
\label{nmo'}
\eea

We want to analyze the asymptotics $m\rightarrow\infty$ of (\ref{intro1'}), allowing
for randomness in the system.
We make the following assumptions on the random instantaneous observable:
\begin{itemize}
\item[(R1)] The operators $M_k$ are RRDO's, and we write the corresponding iid random matrices $M_k=M(\omega_k)$, $k=1,2, \cdots$, .
\item[(R2)] The random operator $N_m(O)$ is independent of the $M_k$ with $1\leq k\leq m-l-1$, and it has the form $N(\omega_{m-l},\ldots,\omega_{m+r})$, where $N:\Omega^{r+l+1}\rightarrow  {\cal B}({\mathbb C}^d)$ is an operator valued random variable.
\end{itemize}

The operator $M_k$ describes the effect of the random $k$-th interaction on $\cS$,
as before. The random variable $N$ in (R2) does not depend on the time step $m$, which is a condition on the observables. It means that the nature of the quantities measured at time $m$ are the same. For instance, the $B^{(j)}_m$ in (\ref{intro0'}) can represent the energy of $\cE_{m+j}$, or the part of the interaction energy $V_{m+j}$ belonging to $\cE_{m+j}$, etc. Both assumptions are verified in a wide variety of physical systems: we may take random interaction times $\tau_k=\tau(\omega_k)$, random coupling operators $V_k=V(\omega_k)$, random energy levels of the $\cE_k$ encoded in $L_{\cE_k}=L_\cE(\omega_k)$, random temperatures $\beta_{\cE_k}=\beta_\cE(\omega_k)$ of the initial states of $\cE_k$, and so on.

The expectation value in any normal state of such instantaneous observables reaches an asymptotic value in the ergodic limit given in the next

\begin{thm}
\label{thmintro2}
Suppose that $\p(M(\omega)\in\cme)\neq 0$. There exists a set $\widetilde{\Omega}\subset\Omega^{\N^*}$ of probability one

s.t. for any $\po\in\widetilde{\Omega}$, for any instantaneous observable $O$, \fer{intro0'}, and for any normal initial state $\varrho$, we have
\begin{equation}
\lim_{\mu\to\infty} \frac{1}{\mu} \sum_{m=1}^\mu \varrho \big( \alpha^m_{\po} (O)\big) =\scalprod{\theta}{{\mathbb E}[N]\psi_\cS},\ \ {\mathbb E}[N]\in\fm_\cS.
\label{intro-1'}
\end{equation}
\end{thm}

{\indent}{\it Remarks} 1. The asymptotic state in which one computes the expectation (w.r.t the randomness) of $N$ is the same as in Theorem \ref{thm4}, with
$\theta=P_{1,{\mathbb E}[M]}^*\psi_\cS$.

2. In case the system is deterministic and ideal, the same result holds, dropping the
expectation on the randomness and taking $\theta=\psi$, as in Theorem \ref{thm0}, see \cite{bjm}.

\subsection{Energy and Entropy Fluxes}

Let us consider some  macroscopic properties of the asymptotic state. The systems we consider may contain randomness, but we drop the variable $\po$ from the notation.

Since we deal with open systems, we cannot speak about its total energy; however, variations in total energy are often well defined. Using an argument of \cite{bjm} one gets a formal expression for the total energy which is constant during all time-intervals $[\tau_{m-1},\tau_m)$, and which undergoes a jump
\be\label{def:energy}
j(m):=\alpha^m(V_{m+1}-V_m)
\ee
at time step $m$.
Hence, the variation of the total energy between the instants $0$ and $m$ is then $\Delta E(m)=\sum_{k=1}^m j(k)$. The relative entropy of $\varrho$ with respect to $\varrho_0$, two normal states on $\fm$, is denoted by ${\rm Ent}(\varrho|\varrho_0)$. Our definition of relative entropy differs from that given in \cite{BR} by a sign, so that in our case, ${\rm Ent}(\varrho|\varrho_0)\geq 0$. For a thermodynamic interpretation of entropy and its relation
to energy, we assume for the next result that $\psi_\cS$
is a $(\beta_\cS,\alpha_\cS^t)$--KMS state on $\fm_\cS$, and that
the $\psi_{\cE_m}$ are $(\beta_{\cE_m}, \alpha_{\cE_m}^t)$--KMS
state on $\fm_{\cE_m}$, where $\beta_\cS$ is the inverse temperature of $\cS$, and $\beta_{\cE_m}$ are
random inverse temperatures of the $\cE_m$.
Let $\varrho_0$ be the state on $\fm$
determined by the vector
$\psi_0=\psi_\cS\otimes\psi_\cc=\psi_\cS\bigotimes_m \psi_{\cE_m}$.
The change of relative entropy is denoted $\Delta S(m) := {\rm Ent} (\varrho\circ\alpha^m| \varrho_0)-{\rm Ent} (\varrho|
\varrho_0)$. This quantity can be expressed in terms of the Liouvillean and interaction operators by means of a formula proven in \cite{JP1}.

One checks that both the energy variation and the entropy variations can be expressed as instantaneous observables, to which we can apply the results of the previous Section.
Defining the asymptotic energy and entropy productions by the limits, if they exist,
\bea
\lim_{m\to\infty} \varrho\left(\frac{\Delta E(m}{m}\right) =: \d E_+ \ \ \ \mbox{and } \ \ \
\lim_{m\to\infty} \frac{\Delta S(m)}{m} =: \d S_+,
\eea
we obtain
\begin{thm}[$2^{\rm nd}$ law of thermodyn\-amics]
\label{thmintro4}
Let $\varrho$ be a normal state on
  $\fm$. Then
\begin{eqnarray*}
\d E_+
&=&
\scalprod{\theta}{\E\big[ P( L_\cS+V-\e^{\i\tau L} (L_\cS+V)\e^{-\i\tau L})P\big]
\psi_\cS}\ \ a.s.\\
 \d S_+ &=&
\scalprod{\theta}{\E\big[ \beta_\cE \, P( L_\cS+V-\e^{\i\tau L} (L_\cS+V)\e^{-\i\tau L})P\big]
\psi_\cS}
\ \ a.s.
\end{eqnarray*}
The energy- and entropy productions  $\d E_+$ and $\d S_+$ are independent of the initial state $\varrho$. If $\beta_\cE$ is deterministic, i.e., $\po$-independent, then the system satisfies the second law of thermodynamics: $\d S_+ = \beta_\ce \d E_+$.
\end{thm}
{\it Remark:} There are explicit examples in which the entropy production can be obtained via rigorous perturbation theory and is proven to be strictly positive, a sure sign that the asymptotic state is a NESS, see \cite{bjm} .

As motivated by (\ref{m11}), the theorems presented in this Sections all rely on
the analysis of products of large numbers of (random) RDO's. The rest of this note is
devoted to a presentation of some of the key features such products have.

\section{Basic Properties of RDO's}

Let us start with a result proven in  \cite{bjm}  as Proposition 2.1.

\begin{lemma}
\label{contraction} Under our general assumptions, the set of matrices $\{M_j\}_{j\in{\mathbb N}^*}$ defined in $(\ref{m11})$ satisfy $M_j\psi_\cS=\psi_\cS$, for all $j\in \N^*$. Moreover, to any $\phi\in \cH_\cS$ there corresponds a unique $A\in
\fm_\cS$ such that $\phi=A\psi_\cS$. $|||\phi|||:=\|A\|_{\cB(\cH_\cS)}$
defines a norm on $\cH_\cS$, and as operators on $\cH_\cS$ endowed with this norm, the $M_j$ are contractions for any $j\in\N^*$.
\end{lemma}

Again,  the fact that $\psi_\cS$ is invariant under $M_j$ is a consequence of (\ref{m8.1}) and their being contractions  comes from the unitarity of the quantum evolution together with the finite dimension of ${\cal H}_\cS$.

As a consequence of the equivalence of the norms $\|\cdot\|$ and $|||\cdot|||$, we get
\begin{cor}\label{ubp}
We have $1\in \sigma(M_j)\subset \{z \ | \ |z|=1\}$ and
\[
\ds \sup\, \{ \|M_{j_n}M_{j_{n-1}}\cdots M_{j_1}\|, \ n\in\N^*, \, j_k\in{\mathbb N}^*\} =C_0<\infty
\]
\end{cor}

Actually, if a set of operators satisfies the bound of the Corollary, it is always possible to construct a norm on ${\mathbb C}^d$ relative to which they are contractions, as proven in the next
\begin{lemma}
Let $R=\{M_j\in M_d({\mathbb C})\}_{j\in J}$, where $J$ is any set of indices
and $C(R)\geq 1$ such that
\begin{equation}\label{estr}
\|M_{j_1} M_{j_2}\cdots M_{j_n}\|\leq C(R),\ \ \forall
\{{j_i}\}_{i=1,\cdots, n}\in J^n, \ \forall n\in{\mathbb N}.
\end{equation}
Then, there exists  a
norm $||| \cdot |||$ on ${\mathbb C}^d$, which depends on $R$,
relative to which the elements of $R$ are
contractions.
\end{lemma}

{\bf Proof:}
Let us define $T\subset M_d({\mathbb C})$ by
\begin{equation}
T=\cup_{n\in {\mathbb N}}\cup_{(j_1, j_2, \cdots j_n)\in
  J^n}M_{j_1}M_{j_2}\cdots M_{j_n}.
\end{equation}
Obviously $R\subset T$, but the identity matrix ${\mathbb I}$ does not
necessarily belong to $T$. Moreover, the estimate (\ref{estr}) still
holds if the $M_{j_i}$'s belong to $T$ instead of $R$.
For any $\varphi\in {\mathbb C}^d$ we set
\begin{equation}
|||\varphi |||=\sup_{M\in T\cup{\mathbb I}}\|M\varphi\|\geq \|\varphi\|,
\end{equation}
which defines a {\it bona fide} norm. Then, for any vector $\varphi$ and any element $N$ of $T$ we compute
\begin{equation}
||| N\varphi |||=\sup_{M\in T\cup{\mathbb I}}\|MN\varphi\|\leq
\sup_{M \in T\cup{\mathbb I}}\|M\varphi\|=|||\varphi |||,
\end{equation}
from which the result follows. {\hfill  {\vrule height 10pt width 8pt depth 0pt}}\\

\noindent {\it Remark.}
If there exists a vector $\psi_S$ invariant under all elements of $R$, it
is invariant under all elements of $T$ and satisfies
$\|\psi_S\|=|||\psi_S|||=1$.

\section{Deterministic Results}
\label{sec:determinist}

In this section, we derive some algebraic formulae and some uniform
bounds for later purposes. Since there
is no probabilistic issue involved here, we shall therefore
simply denote
$M_j=M(\omega_j)$. We are concerned with the product
\be\label{def:psi}
\Psi_n:= M_1 \cdots M_n.
\ee

\subsection{Decomposition of the $M_j$}
\label{ssec:notation}

With $P_{1,M_j}$ the spectral projection of $M_j$ for the eigenvalue $1$ we define
\be\label{defpsi}
\psi_j:= P^*_{1,j}\psi_\cS, \ \ \ \ P_j:=|\psi_\cS\ket\bra \psi_j|.
\ee
Note that $\bra \psi_j|\psi_\cS\ket=1$ so that $P_j$ is a projection and, moreover, $M_j^*\psi_j=\psi_j$.  We introduce the following decomposition of $M_j$
\be\label{struct}
M_j:=P_j+Q_jM_jQ_j,  \ \ \ \mbox{with} \ \ \ Q_j=\one-P_j.
\ee
We denote the part of $M_j$ in $Q_j\C^d$, by
$M_{Q_j}:=Q_jM_jQ_j$.
It easily follows from these definitions that
\bea
P_jP_k=P_k,  & & \phantom{x}Q_jQ_k=Q_j, \label{eq:ppqq}\\
Q_jP_k=0,\phantom{i} & & \phantom{x}P_kQ_j=P_k-P_j=Q_j-Q_k. \label{eq:pqqp}
\eea

\noindent {\it Remark.}
If $1$ is a simple eigenvalue, $P_{1,M_j}=P_j$ and (\ref{struct}) is a (partial) spectral decomposition of $M_j$.

\begin{proposition}
\label{prop:psiform}
For any $n$,
\be\label{eq:psi}
\Psi_n=|\psi_\cS\ket\bra\theta_n|+M_{Q_1}\cdots \mqn,
\ee
where
\bea
\theta_n & = & \psi_n+M_{Q_n}^*\psi_{n-1}+\cdots +M_{Q_n}^*\cdots M_{Q_2}^* \psi_1 \label{eq:theta1}\\
 & = & M_n^*\cdots M_2^* \psi_1
\label{eq:theta2}
\eea
and where $\bra\psi_\cS,\theta_n\ket=1$.
\end{proposition}

\proof Inserting the decomposition (\ref{struct}) into (\ref{def:psi}), and using \fer{eq:ppqq}, \fer{eq:pqqp}, we have
\be
\Psi_n= \sum_{j=1}^n P_j M_{Q_{j+1}}\cdots M_{Q_n} +M_{Q_1}\cdots \mqn.\nonumber
\ee
Since $P_j=|\psi_\cS\ket\bra \psi_j|,$ this proves (\ref{eq:psi}) and (\ref{eq:theta1}). From (\ref{eq:pqqp}), we obtain for any $j,k$,
\be
\label{mqm}
M_{Q_j}M_{Q_k}=M_{Q_j}M_k=Q_jM_jM_k.
\ee
Hence, $\Psi_n = P_1 M_1\cdots M_n +Q_1 M_1\cdots M_n = |\psi_\cS\ket\bra M_n^*\cdots M_2^* \psi_1| + M_{Q_1}\cdots \mqn$,
which proves (\ref{eq:theta2}).
\qed

\subsection{Uniform Bounds}\label{ssec:unifbound}

The operators $M_j$, and hence the product $\Psi_n$, are contractions on $\C^d$ for the norm $|||\cdot |||$.  In order to study their asymptotic
behaviour, we need some uniform bounds on the $P_j, Q_j,\ldots$

Recall  that $\|\psi_\cS\|=1$.

\begin{proposition}\label{prop:unifbound} Let $C_0$ be as in Corollary \ref{ubp}. Then, the following bounds hold
\begin{enumerate}
\item  For any $n\in \N^*$,  $\|\Psi_n\|\leq C_0$.
\item For any $j\in\N^*$, $\|P_j\|=\|\psi_j\| \leq C_0$ and $\|Q_j\|\leq 1+C_0$.
\item $\ds \sup\, \{\|M_{Q_{j_n}}M_{Q_{j_{n-1}}}\cdots M_{Q_{j_1}}\|, \ n\in\N^*,\, j_k\in{\mathbb N}^*\} \leq C_0(1+C_0)$.
\item For any $n\in\N^*$, $\|\theta_n\|\leq C_0^2$.
\end{enumerate}
\end{proposition}

\proof It is based on Von Neumann's ergodic Theorem, which states that
\[
P_{1,M_j}=\lim_{N\ra\infty}\frac{1}{N}\sum_{k=0}^{N-1}M_j^k.
\]
The first two estimate easily follow, whereas the third makes use of
(\ref{mqm}) to get
$M_{Q_{j_n}}M_{Q_{j_{n-1}}}\cdots M_{Q_{j_1}}=Q_{j_n}M_{j_n}M_{j_{n-1}}\cdots M_{j_1},$
so that
\[
\|M_{Q_{j_n}}M_{Q_{j_{n-1}}}\cdots M_{Q_{j_1}}\|\leq \|Q_{j_n}\|C_0\leq C_0(1+C_0).
\]
Finally, (\ref{eq:theta2}) and the above estimates yield $\|\theta_n\|\leq C_0\|\psi_1\|\leq C_0^2$.
\qed

\subsection{Asymptotic Behaviour}\label{ssec:asympt}

We now turn to the study of the asymptotic behaviour of $\Psi_n$, starting with the simpler case of {\em Ideal Repeated Interaction Quantum Systems}.

That means we assume
\be
M_k= M, \  \ \forall k\geq 1.
\ee
If $1$ is a simple eigenvalue of $M$, then $P_{1,M}=|\psi_\cS\ket\bra \psi|$,
for some $\psi$ s.t. $\bra\psi |\psi_\cS\ket=1$,
and
\be
\Psi_n=M^n=|\psi_\cS\ket\bra \psi|+M_Q^n
\ee
Further, if all other eigenvalues of $M$ belong to the open unit disk,  $M_Q^n$ converges exponentially fast to zero as $n\ra \infty$.

Consequently, denoting by $\mbox{spr}(N)$ the spectral radius of $N\in M_d({\mathbb C})$,
\begin{lem} If the {\em RDO} $M$ belongs to $\cme$,
\be
\Psi_n=|\psi_\cS\ket\bra \psi|+O(e^{-\gamma n}),
\ee
for all $0<\gamma<1-\mbox{\em spr}(M_Q)$.
\end{lem}

Two things are used above, the decay of $M_Q^n$ and the fact that $\theta_n=\psi$ is constant, see (\ref{eq:psi}). The following result shows that in general, if one knows {\em a priori} that the products of $M_{Q_j}$'s in (\ref{eq:psi}) goes to zero, $\Psi_n$ converges if and only if $P_n=|\psi_\cs\ket\bra\psi_n |$, does.

\begin{proposition}
\label{limpsi}
Suppose that $\lim_{n\to\infty} \sup \{\|M_{Q_{j_n}}\cdots M_{Q_{j_1}}\|, \ j_k\in\N^*\}=0$. Then $\theta_n$ converges if and only if $\psi_n$ does. If they exist, these two limits coincide, and thus
\[
\lim_{n\ra\infty}\Psi_n=|\psi_\cS\ket\bra \psi_\infty|,
\]
where $\psi_\infty=\lim_{n\rightarrow\infty} \psi_n$. Moreover, $|\psi_\cS\ket\bra \psi_\infty|$ is a projection.
\end{proposition}

In general, we cannot expect  pointwise convergence of the $\theta_n$, but we can consider an ergodic average of $\theta_n$ instead. This is natural in terms of dynamical systems, a fluctuating system does not converge.

The previous convergence results relies on the
decay of the product of operators $M_{Q_j}$.
Conditions ensuring this are rather strong. However, Theorem \ref{thm1} below shows that in the {\it random setting}, a similar exponential decay holds under rather weaker assumptions.

\section{Random Framework}

\subsection{Product of Random Matrices}

We now turn to the random setup in the framework of Section \ref{rsetup}. For $M(\omega)$ an RRDO, with probability space $(\Omega,\cF,\p)$,
we consider the RRDP on ${\Omega}^{{\mathbb N}^*}$ given by
\[
\Psi_n(\po):=M(\omega_1)\cdots M(\omega_n),\qquad \po\in{\Omega}^{{\mathbb N}^*}.
\]

We show that $\Psi_n$ has a decomposition into an exponentially decaying part and a fluctuating part.
Let $P_{1}(\omega)$ denote the spectral projection of $M(\omega)$ corresponding to the eigenvalue one ($\dim P_1(\omega)\geq 1$), and let $P^*_1(\omega)$ be its adjoint operator. Define
\begin{equation}
\psi(\omega) := P_1(\omega)^*\psi_\cS,
\label{m13}
\end{equation}
and set
\bea
P(\omega)=|\psi_\cs\rangle \langle\psi(\omega)|, \ \ \
Q(\omega)=\one-P(\omega).
\eea
The vector $\psi(\omega)$ is normalized as $\scalprod{\psi_\cS}{\psi(\omega)}=1$. We decompose $M(\omega)$ as
\begin{equation}
M(\omega) = P(\omega)+Q(\omega)M(\omega)Q(\omega)=: P(\omega) +M_Q(\omega).
\label{m14}
\end{equation}
Taking into account this decomposition, we obtain (c.f. Proposition \ref{prop:psiform})
\begin{equation}
\Psi_n(\po):=M(\omega_1)\cdots M(\omega_n) = |\psi_\cS\rangle\langle\theta_n(\po)| + M_Q(\omega_1)\cdots M_Q(\omega_n),
\label{m15}
\end{equation}
where $\theta_n(\po)$ is the Markov process
\bea
\theta_n(\po) &=&M^*(\omega_n)\cdots M^*(\omega_2)\psi(\omega_1)\\ \nonumber&=&\psi(\omega_n)+
M_{Q}^*(\omega_n)\psi(\omega_{n-1})+\cdots +M_{Q}^*(\omega_n)\cdots M_{Q}^*(\omega_2) \psi(\omega_1) ,
\label{m16}
\eea
$M^*(\omega_j)$ being the adjoint operator of $M(\omega_j)$. We analyze the two parts in the r.h.s. of \fer{m15} separately.

\begin{thm}[Decaying process]
\label{thm1}
Let $M(\omega)$ be a random reduced dynamics operator. Suppose that $\p(M(\omega)\in\cme)>0$.
Then there exist a set $\Omega_1\subset\Omega^{\N^*}$ and constants $C,\alpha>0$ s.t. ${\mathbb P}(\Omega_1)=1$ and s.t. for any $\po\in\Omega_1$, there exists a random variable $n_0(\omega)$ s.t. for any $n\geq n_0(\po)$,
\begin{equation}
\| M_{Q}(\omega_1)\cdots M_{Q}(\omega_n)\|\leq C\e^{-\alpha n},
\label{m17}
\end{equation}
and ${\mathbb E}[e^{\alpha n_0}]<\infty$. Moreover, ${\mathbb E}[M]\in\cme$.
\end{thm}

\noindent {\it Remarks.}  1.  The sole condition of $M$ having an arbitrarily small, non-vanishing probability to be in $\cme$ suffices to guarantee the exponential decay of the product in \fer{m17} and that ${\mathbb E}[M]$ belongs to $\cme$.

2. Actually, ${\mathbb E}[M]\in\cme$ is a consequence of $\mbox{spr}({\mathbb E}[M_Q])<1$, which comes as a by product of the proof of Theorem \ref{thm1}.
From the identities
\be \label{idmoy}
{\mathbb E}[M]=|\psi_\cS\ket\bra{\mathbb E}[\psi]|+{\mathbb E}[M_Q], \ \ \
 \bra{\mathbb E}[\psi]| \psi_\cS\ket=1,  \ \ \ {\mathbb E}[M_Q]\psi_\cS=0,
\ee which {\it do not } correspond to a (partial) spectral decomposition of ${\mathbb E}[M]$, and this estimate, we get
\bea
{\mathbb E}[M]^n&=&|\psi_\cS\ket\bra\ {\mathbb E}[\psi]+{\mathbb E}[M_Q]^*{\mathbb E}[\psi]+\cdots {{\mathbb E}[M_Q]^*}^{n-1}{\mathbb E}[\psi]\ |+{{\mathbb E}[M_Q]^*}^{n}\nonumber\\ \label{pem}
&{\rightarrow \atop n\ra\infty}& |\psi_\cS\ket\bra({\mathbb I}-{\mathbb E}[M_Q]^*)^{-1}{\mathbb E}[\psi]|\equiv P_{1, {\mathbb E}[M]}.
\eea

3. Our choice \fer{m13} makes $\psi(\omega)$ an eigenvector of $M^*(\omega)$. Other choices of (measurable) $\psi(\omega)$ which are bounded in $\omega$ lead to different decompositions of $M(\omega)$, and can be useful as well. In particular, if $M(\omega)$ is a bistochastic matrix, $\psi(\omega)$ can be chosen as an $M^*(\omega)$-invariant vector which is independent of $\omega$.

\subsection{A Law of Large Numbers}

\medskip
\noindent
We now turn to the asymptotics of the Markov process \fer{m16}.

\begin{thm}[Fluctuating process]
\label{thm2}
Let $M(\omega)$ be a random reduced dynamics operator s.t. that $\p(M(\omega)\in\cme)>0$. There exists a set $\Omega_2\subset\Omega^{\N^*}$ s.t. ${\mathbb P}(\Omega_2)=1$ and, for all $\po\in\Omega_2$,
\begin{equation}
\lim_{N\rightarrow\infty}\frac 1N\sum_{n=1}^N\theta_n(\po) = \theta,
\label{m21}
\end{equation}
where
\begin{equation}
\theta = \lim_{n\ra\infty}{\mathbb E}[\theta_n]

=P^*_{1,{\mathbb E}[M]}{\mathbb E}[\psi]=P^*_{1,{\mathbb E}[M]}\psi_\cS.
\label{m21.01}
\end{equation}
\end{thm}

\medskip
\noindent {\it Remarks:} 1.
 The ergodic average limit of $\theta_n(\po)$ does not depend on the particular choice of $\psi(\omega)$. This follows from the last equality in \fer{m21.01}.

2. The second  equality in (\ref{m21.01}) stems from
\be
{\mathbb E}[\theta_n]=\sum_{k=0}^{n-1}({\mathbb E}[M_Q])^k{\mathbb E}[\psi],
\ee
by independence, and which converges to $P_{1, {\mathbb E}[M]}^*{\mathbb E}[\psi]$ by (\ref{pem}). The third equality follows from (\ref{idmoy}).

3. Comments on the proof of these Theorems are provided below.

\medskip
\noindent
Combining Theorems \ref{thm1} and \ref{thm2} we immediately get the following result.

\begin{thm}[Ergodic theorem for RRDP]
\label{thm3}
Let $M(\omega)$ be a random reduced dynamics operator. Suppose  $\p(M(\omega)\in\cme)>0$. Then there exists a set $\Omega_3\subset\Omega^{\N^*}$ s.t. ${\mathbb P}(\Omega_3)=1$ and, for all $\po\in\Omega_3$,
\begin{equation}
\lim_{N\rightarrow\infty}\frac 1N\sum_{n=1}^N M(\omega_1)\cdots
M(\omega_n) =|\psi_\cS\ket\bra \theta|=P_{1,{\mathbb E}[M]}.
\label{m21.1}
\end{equation}
\end{thm}

\noindent {\it Remarks\ } 1. If one can choose $\psi(\omega)\equiv\psi$ to be independent of $\omega$, then we have by  (\ref{eq:theta2}) that $\theta_n(\po)=\psi$, for all $n,\po$. Thus,  from \fer{m15}-\fer{m17}, we get the stronger result
$
\lim_{n\rightarrow\infty} M(\omega_1)\cdots
M(\omega_n)= |\psi_\cS\ket\bra \psi|$, a.s., exponentially fast.

2. This result can be viewed as a strong law of large numbers for the matrix valued process $\Psi_n(\po)=M(\omega_1)\cdots M(\omega_n)$.\medskip

\noindent{\bf Comments:}
The existence of (ergodic) limits of products of random operators is known for a long time and under very general conditions, see e.g. \cite{beckschwarz} ,  \cite{k} . However, the explicit value of the limit depends on the detailed properties of the set of random matrices considered. The point of our analysis is thus the explicit determination of the limit   (\ref{m21.1}) which is crucial for the applications to the dynamics of random repeated interaction quantum systems.

The more difficult part of this task is to prove Theorem \ref{thm1}. The idea consists  in identifying matrices in the product $\Psi_n(\po)$ which are equal (or close) to a fixed matrix $M$ that belongs to $\cme$. Consecutive products of $M$ give an exponential decay, whereas products of other matrices are uniformly bounded. Then one shows that the density of long strings of consecutive $M$'s in a typical sample is finite.
Once this is done, a self-contained proof of Theorem \ref{thm3}, is not very hard to get  \cite{bjm2} .\\

On the other hand, given Theorem \ref{thm1} and the existence result of \cite{beckschwarz} , we can  deduce Theorem \ref{thm3} as follows.  Let us state
the result of Beck and Schwarz in our setup. Let $T$ denote the usual shift operator on $\Omega^{{\mathbb N}^*}$ defined by $(T\po)_j=\po_{j+1}$, $j=1,2, \cdots$.
\begin{thm}[Beck and Schwartz\cite{beckschwarz}] Let $M(\omega)$ be a random reduced dynamics operator on $\Omega$.  Then there exists a matrix valued random variable
$L(\po)$ on $\Omega^{{\mathbb N}^*}$, s.t.   ${\mathbb E}[\|L\|]<\infty$, which satisfies almost surely
\be\label{proT}
L(\po)=M(\omega_1)L(T\po),
\ee
where $T$ is the shift operator, and
\be
\lim_{N\rightarrow\infty}\frac 1N\sum_{n=1}^N M(\omega_1)\cdots
M(\omega_n) =L(\po).
\ee
\end{thm}
Further assuming  the hypotheses of Theorem \ref{thm1},  and making use of
the decomposition (\ref{m15}), we  get that $L$ can be written as
\be
L(\po)=|\Psi_{\cS}\ket\bra \theta(\po)|,
\ee
for some random vector $\theta(\po)$.  Now, due to (\ref{proT}) and the fact that $\psi_\cS$ is invariant, $\theta(\po)$ satisfies
\be
\theta(\po)=\theta(T\po) \ \ \mbox{a.s.}
\ee
The shift being ergodic, we deduce that $\theta$ is constant a.s., so that
\be
\theta(\po)={\mathbb E}[\theta] \ \ \mbox{a.s.}
\ee
which, in turn, thanks to Proposition \ref{prop:unifbound} and Lebesgue dominated convergence Theorem, allows to get from (\ref{m16})
\be
{\mathbb E}[\theta]=\lim_{n\ra\infty}{\mathbb E}[\theta_n]=P^*_{1,{\mathbb E}[M]}\Psi_{\cS}.
\ee

\subsection{Limit in Law and Lyapunov Exponents}\label{ssec:met}

We present here results for products ``in reverse order'' of the form
$\Phi_n(\po):= M(\omega_n) \cdots M(\omega_1)$, which have the same law as $\Psi_n(\po)$.
They also yield information about the Lyapunov exponent of the process. The following results are standard, see  e.g. \cite{la} . The limits
\[
\Lambda_\Phi(\po)=\lim_{n\ra\infty}(\Phi_n(\po)^*\Phi_n(\po))^{1/2n} \ \  {\rm\  and\ } \ \
\Lambda_\Psi(\po)=\lim_{n\ra\infty}(\Psi_n(\po)^*\Psi_n(\po))^{1/2n}
\]
exist almost surely, the top Lyapunov exponent $\gamma_1(\po)$ of $\Lambda_\Phi(\po)$
coincides with that of $\Lambda_\Psi(\po)$, it  is constant a.s., and so is its multiplicity. It is in general difficult to prove
that the multiplicity of $\gamma_1(\po)$ is $1$.

\begin{thm}
\label{prop:randlyap}
Suppose $\p(M(\omega)\in\cme)>0$. Then there exist $\alpha>0$, a random vector
\be
\eta_\infty(\po)=\lim_{n\ra\infty}\psi(\omega_1)+
M_{Q}^*(\omega_1)\psi(\omega_{2})+\cdots +M_{Q}^*(\omega_1)\cdots M_{Q}^*(\omega_{n-1}) \psi(\omega_n)
\ee
and $\Omega_4\subset\Omega^{{\mathbb N}^*}$ with $\P(\Omega_4)=1$ such that for any $\po\in\Omega_4$ and $n\in\N^*$
\be\label{phicvg}
\Big\| \Phi_n(\po)- |\psi_\cS\ket\bra\eta_\infty(\po)| \Big\| \leq C_{\po} e^{-\alpha n}, \ \ \mbox{for some } \  C_{\po}.
\ee
As a consequence, for any  $\po\in\Omega_4$, $\gamma_1(\po)$ is of multiplicity one.
\end{thm}

\noindent{\bf Comments:}
While the Theorems above on the convergence of asymptotic states give us
the comfortable feeling provided by almost sure results, it is an important
aspect of the theory to understand the fluctuations around the asymptotic
state the system reaches almost surely. In our iid setup, the law of the
product $\Psi_n(\po)$ of RRDO's coincides with the law of $\Phi_n(\po)$ which
converges exponentially fast to $ |\psi_\cS\ket\bra\eta_\infty(\po)|$.
Therefore, the fluctuations are encoded in the law of the random vector
$\eta_\infty(\po)$.  It turns out it is quite difficult, in general, to get informations about this law. There are partial results only about certain aspects of the law of such random vectors in case they are obtained by means of matrices belonging to some subgroups of $Gl_d(\mathbb R)$ satisfying certain irreducibility conditions, see e.g. \cite{dsetal}. However, these results do not apply to our RRDO's.

\subsection{Generalization}

A generalization of the analysis performed for observables acting on $\cS$ only described above allows to establish the following corresponding results when instantaneous observables are considered.

The asymptotics of the dynamics \fer{intro1'}, in the random case, is encoded in the product
\[
M(\omega_1)\cdots M(\omega_{m-l-1})N(\omega_{m-l},\ldots,\omega_{m+r}),
\]
where $N:\Omega^{r+l+1}\ra M_d({\mathbb C})$ is given in assumption (R2).

\begin{thm}[Ergodic limit of infinite operator product] \ \\
\label{thmintro1} Assume $M(\omega)$ is a RRDO and (R2) is satisfied. Suppose that $\p(M(\omega)\in\cme)\neq 0$. Then ${\mathbb E}[M]\in\cme$. Moreover, there exists a set ${\Omega}_5 \subset
 \Omega^{\N^*}$ of probability one

s.t. for any $\po=(\omega_n)_{n\in\mathbb N}\in{\Omega}_5$,
\begin{equation*}
\lim_{\nu\rightarrow\infty}\frac 1\nu\sum_{n=1}^\nu M(\omega_1)\cdots
M(\omega_n) N(\omega_{n+1},\ldots,\omega_{n+l+r+1})= |\psi_\cS\ket\bra \theta|\ \E[N],
\end{equation*}
where $\theta = P^*_{1,{\mathbb E}[M]}\psi_\cS$.
\end{thm}

As in the previous Section, a density argument based on the cyclicity and separability of the
reference vector $\psi_0$ allows to obtain from Theorem \ref{thmintro1} the asymptotic state
for all normal initial states $\varrho$ on $\fm$ given as  Theorem \ref{thmintro2}

\bigskip
{\bf Acknowledgements.\ }

I wish to thank I. Beltita, G. Nenciu and R. Purice who organized the 10th edition of  QMath for their kind invitation and  L. Bruneau and M. Merkli for a very enjoyable collaboration.


text:
\begin{abstract}

In this work, we obtain sufficient conditions for the ``stability" of our recently proposed algorithms,  modified-CS (for noisy measurements) and Least Squares CS-residual (LS-CS), designed for recursive reconstruction of sparse signal sequences from noisy measurements. By ``stability" we mean that the number of misses from the current support estimate and the number of extras in it remain bounded by a time-invariant value at all times. The concept is meaningful only if the bound is small compared to the current signal support size. A direct corollary is that the reconstruction errors are also bounded by a time-invariant and small value.

\end{abstract}

\section{Introduction}
In this work, we study the ``stability" of modified-CS (noisy) \cite{modcsjp,modcsicassp10} and of LS-CS-residual (LS-CS) \cite{just_lscs,kfcsicip,kfcspap} which were designed for recursive reconstruction of sparse signal sequences from noisy measurements. By ``stability" we mean that the number of misses from the current support estimate and the number of extras in it remain bounded by a {\em time-invariant} value at all times. The concept is meaningful only if the bound is small compared to the current signal support size. A direct corollary is that the reconstruction errors are also bounded by a time-invariant and small value.

The key assumption that our algorithms utilize is that the support changes slowly over time. As we demonstrated in \cite{just_lscs,modcsjp}, this assumption holds for many medical image sequences. Denote the support estimate from the previous time by $T$. Modified-CS tries to finds a signal that is sparsest outside of $T$ and satisfies the data constraint. LS-CS uses a different approach. It replaces compressive sensing (CS) on the observation by CS on the least squares (LS) residual computed using  $T$. Both algorithms are able to achieve greatly reduced reconstruction error compared to simple CS (CS at each time separately) when using fewer measurements than what CS needs.

Other algorithms for recursive reconstruction include our older work on Kalman filtered CS-residual (KF-CS) \cite{kfcsicip,kfcspap}; CS for time-varying signals \cite{giannakis_2} (assumes a time-invariant support, which is a somewhat restrictive assumption); homotopy methods \cite{romberg} (use past reconstructions to speed up current optimization but not to improve reconstruction error with fewer measurements); and \cite{ibm} (a recent modification of KF-CS). Two other algorithms that are also designed for static CS with partial knowledge of support include \cite{camsap07} and \cite{hassibi}. The work of \cite{camsap07} proposed an approach similar to modified-CS but did not analyze it and also did not show real experiments either. The work of \cite{hassibi}, which appeared in parallel with modified-CS, assumed a probabilistic prior on the support and obtained conditions for exact reconstruction.

To the best of our knowledge, stability of recursive sparse reconstruction algorithms has not been studied in any other work except in our older works \cite{just_lscs,kfcspap} for LS-CS and KF-CS respectively.

The KF-CS result \cite{kfcspap} is under fairly strong assumptions, e.g. it is for a random walk signal change model with only support additions (no removals). The result for LS-CS stability \cite{just_lscs} holds under mild assumptions and is for a fairly realistic signal change model. The only limitation is that it assumes that support changes occur ``every-so-often": every $d$ time units, there are $S_a$ support additions and $S_a$ removals.
 But from testing the slow support change assumption for real data (medical image sequences), it has been observed that support changes usually occur at {\em every} time, e.g. see Fig. 1 of \cite{just_lscs}. {\em This important case is the focus of the current work.}

In \cite{just_lscs}, we only studied LS-CS (modified-CS was proposed later). But the techniques of \cite{just_lscs} can be also used to show modified-CS stability for the model of \cite{just_lscs}.
In this work, we show the stability of both LS-CS and modified-CS and of its improved version, ``modified-CS with add-LS-del". We first discuss modified-CS since, from experiments, it is known to be a better algorithm. In facts its stability result is also better (holds under weaker assumptions).

The paper is organized as follows. We give problem definition in Sec. \ref{notn} and we overview our results in Sec. \ref{overview}. We describe the signal model for proving stability in Sec. \ref{signalmodel}. We obtain sufficient conditions for the stability of modified-CS and discuss the implications in Sec. \ref{simple_modcs}. We discuss some of its limitations and develop a simple modification that uses a better support estimation approach (modified-CS with add-LS-del). This support estimation approach is related to the one in \cite{cosamp,kfcsicip,just_lscs}. In Sec. \ref{addLSdel_modcs}, we show the stability of modified-CS with add-LS-del, which is more difficult to do. The result for LS-CS stability is obtained in Sec. \ref{addLSdel_lscs}. Numerical experiments are discussed in Sec. \ref{sims}. Conclusions are given in Sec. \ref{conclusions}.

\subsection{Notation and Problem Definition}
\label{notn}
The set operations $\cup$, $\cap$, $\setminus$ have their usual meanings. $\emptyset$ denotes the empty set.
We use $T^c$ to denote the complement of a set $T$ w.r.t. $[1,m]:=[1,2,\dots m]$, i.e. $T^c := [1,m] \setminus T$. $|T|$ denotes the cardinality of $T$. For a vector, $v$, and a set, $T$, $v_T$ denotes the $|T|$ length sub-vector containing the elements of $v$ corresponding to the indices in the set $T$. $\| v \|_k$ denotes the $\ell_k$ norm of a vector $v$. {\em If just $\|v\|$ is used, it refers to $\|v\|_2$.} Similarly, for a matrix $M$, $\|M\|_k$ denotes its induced $k$-norm, while just $\|M\|$ refers to $\|M\|_2$. $M'$ denotes the transpose of $M$ and $M^\dag$ denotes the Moore-Penrose pseudo-inverse of $M$ (when $M$ is tall, $M^\dag:=(M'M)^{-1} M'$). For a fat matrix $A$, $A_T$ denotes the sub-matrix obtained by extracting the columns of $A$ corresponding to the indices in $T$.
The $S$-restricted isometry constant \cite{dantzig}, $\delta_S$, for an $n \times m$ matrix (with $n<m$), $A$, and the $S,S'$ restricted orthogonality constant \cite{dantzig}, $\theta_{S,S'}$, are as defined in \cite[eq 1.3]{dantzig} and \cite[eq 1.5]{dantzig} respectively.

We assume the following observation model:
\bea
y_t = A x_t + w_t,  \ \|w_t\| \le \eps

\label{obsmod}
\eea
where $x_t$ is an $m$ length sparse vector with support $N_t$, $y_t$ is the $n< m$ length observation vector at time $t$ and $w_t$ is observation noise with $\|w_t\| \le \eps$.  ``Support" refers to the set of indices of the nonzero elements of $x_t$.

Our goal is to recursively estimate $x_t$ using $y_1, \dots y_t$. By {\em recursively}, we mean, use only $y_t$ and the estimate from $t-1$, $\xhat_{t-1}$, to compute the estimate at $t$.

As we explain in Sec. \ref{simple_modcs}, our algorithm need more measurements at the initial time, $t=0$. We use $n_0$ to denote the number of measurements used at $t=0$ and we use $A_0$ to denote the corresponding $n_0 \times m$ measurement matrix.
We use $\alpha$ to denote the support estimation threshold used by modified-CS and we use $\alpha_{add}, \alpha_{del}$ to denote the support addition and deletion thresholds used by modified-CS with add-LS-del and by LS-CS.

We use $\xhat_t$ to denote the final estimate of $x_t$ at time $t$ and $\Nhat_t$ to denote its support estimate. To keep notation simple, we avoid using the subscript $t$ wherever possible.

\bd[$T$, $\Delta$, $\Delta_e$]
We use $T  : = \Nhat_{t-1}$ to denote the support estimate from the previous time.
We use $\Delta := N_t \setminus T$ to denote the unknown part of the support at the current time and $\Delta_e := T \setminus N_t$ to denote the ``erroneous" part of $T$. We attach the subscript $t$ to the set, e.g. $T_t$ or $\Delta_t$, where necessary.
\ed
\bd[$\tT$, $\tDelta$, $\tDelta_e$]
We use $\tT := \Nhat_t$ to denote the final estimate of the current support; $\tDelta : = N_t \setminus \tT$ to denote the ``misses" in $\Nhat_t$ and $\tDelta_e := \tT \setminus N_t$ to denote the ``extras".
\ed
The sets $T_\dett, \Delta_\dett, \Delta_{e,\dett}$ are defined later in Sec. \ref{addLSdel_modcs}.

{\em If the sets $B,C$ are disjoint, then  we just write $D \cup B \setminus C$ instead of writing $(D \cup B) \setminus C$, e.g. $N_t = T \cup \Delta \setminus \Delta_e$.}

We refer to the left (right) hand side of an equation or inequality as LHS (RHS).

\vspace{-0.1in}
\subsection{Overview of Results}
\label{overview}

When measurements are noisy, the reconstruction errors of modified-CS (noisy) and of LS-CS have been bounded as a function of $|N_t|$, $|\Delta_t|$ and $|\Delta_{e,t}|$ in \cite{modcsicassp10,arxiv} and in \cite{just_lscs} respectively. The bound is small if $|\Delta_t|$ and  $|\Delta_{e,t}|$ are small enough. But smallness of the support errors, $\Delta_t$, $\Delta_{e,t}$, depends on the accuracy of the previous reconstruction. Thus it can happen that the error bound increases over time, and such a bound is of limited use for a recursive reconstruction problem. There is thus a need to obtain conditions under which one can show ``stability", i.e. obtain a time-invariant bound on the sizes of these support errors. Also, for the result to be meaningful, the support errors' bound needs to be small compared to the support size.

In this work, we study the stability of modified-CS for noisy measurements and its modification, modified-CS with add-LS-del, as well as of LS-CS. This is done under a bounded observation noise assumption and for a signal model with
\ben
\item support changes ($S_a$ additions and $S_a$ removals) occurring at every time, $t$,
\item magnitude of the newly added coefficients increases gradually, and similarly for decrease before removal,
\item support size is $S_0$ at all times and the signal power is also constant
\een
\begin{remark}
The reason we need the bounded noise assumption is as follows. When the noise is unbounded, e.g. Gaussian, all error bounds for CS and, similarly, all error bounds for LS-CS or modified-CS hold with ``large probability" \cite{dantzig,candes_rip,tropp,just_lscs,modcsicassp10,arxiv}. To show stability, we need the error bound for LS-CS or modified-CS to hold at all times, $0 \le t < \infty$ (this, in turn, is used to ensure that the support gets estimated with bounded error at all times). Clearly this is a zero probability event.
\end{remark}

Our results have the following form. For a given number and type of measurements (i.e. for a given measurement matrix, $A$), and for a given noise bound, $\eps$, if,
\ben
\item the support estimation threshold(s) is/are large enough,
\item the support size, $S_0$, and support change size, $S_a$ are small enough,
\item the newly added coefficients increase (existing large coefficients decrease) at least at a certain rate, $r$, and
\item the initial number of measurements, $n_0$, is large enough for accurate initial reconstruction using simple CS,
\een
then the support errors are bounded by time-invariant values. In particular, we show that $|N_t \setminus \Nhat_t| \le 2S_a$ and $|\Nhat_t \setminus N_t| = 0$. Consequently the reconstruction error is also bounded by a small and time-invariant value.

A key assumption used in designing both modified-CS and LS-CS is that the signal support changes slowly over time. As shown in \cite{just_lscs,modcsjp}, this holds for real medical image sequences. For our model, this translates to $S_a \ll S_0$.

Under the slow support change assumption, clearly, $2S_a \ll S_0$, and so the support error bounds are small compared to the support size, $S_0$, making our stability results meaningful. We also compare the conditions on $S_0$ required by our results with those required by the corresponding simple CS error bounds (since simple CS is not a recursive approach these also serves as a stability result for simple CS) and argue that our results hold under weaker assumptions (allow larger values of $S_0$). The results for modified-CS, modified-CS (with add-LS-del) and LS-CS are also compared.

config: arxiv


TITLE: Strictly positive Riemann integrable Function
QUESTION [6 upvotes]: I read a good number of posts which deal with this specific topic, but none of them seem to answer my question. If this is a repost, I apologize.
Alright so here is the problem, followed by a theorem which I use, and then my attempted proof:

Exercise 7.4.4. Show that if $f(x)>0$ for all $x\in [a,b]$ and $f$ is integrable, then $\int_{a}^{b} f>0$.

The theorem (and exercise) is from Abbott's Understanding Analysis, and my proof uses Theorem 7.4.2(ii):

Theorem 7.4.2.(ii) Assume $f$ is integrable on $[a,b]$. If $m\leq f(x)\leq M$ for all $x\in [a,b]$ then
$$m(b-a)\leq\int_a^b f(x) \leq M(b-a)$$

Now here is my proof:

Proof. Let $f(x)>0$ for all $x\in [a,b]$ and assume $f$ is integrable. Since $f$ is integrable, then we can let (but can we?)
$$m=\inf\{f(x_0):x_0 \in [a,b]\}\text{ and  }M=\sup\{f(x_0):x_0\in [a,b]\}$$
Where both $m$ and $M$ are greater than zero since $f(x)>0$.
Now by Theorem 7.4.2.(ii), we can write $$m(b-a)\leq \int_{a}^{b} f\leq M(b-a)$$
And since $0<m(b-a)\leq M(b-a)$, then the integral must be greater than zero as well.
Q.E.D.

I would just like some verification/correction. My doubt is whether or not the values $m$ and $M$ necessarily have to exist, since Theorem 7.4.2.(ii) states that the inequality is only true IF there exists such values for $m$ and $M$. But since $f$ is integrable and $[a,b]$ is compact, then the function should attain a maximum and a minimum, correct?

REPLY [7 votes]: That is not correct. Since Riemann integrability implies boundedness, both infimum and supremum exist, but if we let $f(x)=x$ for $x\in(0,1]$ and $f(0)=1$, unfortunately, $\inf_{x\in[0,1]}f(x)=0$ and the infimum is not attainable.
Elementary Way?
Assume the contrary that $\displaystyle\int_{a}^{b}f(x)dx=0$, then find a partition $P=\{x_{0},...,x_{n}\}$ such that $U(f,P)\leq b-a$. It cannot be the case that all $\sup_{x\in[x_{i-1},x_{i}]}f(x)>1$, $i=1,...,n$, so some $i$ is such that $\sup_{x\in[x_{i-1},x_{i}]}f(x)\leq 1$, let us write $\sup_{x\in[a_{1},b_{1}]}f(x)\leq 1$.
Now $\displaystyle\int_{a_{1}}^{b_{1}}f(x)dx=0$. Choose another partition $Q$ in $[a_{1},b_{1}]$ such that $U(f,Q)\leq\dfrac{b_{1}-a_{1}}{2}$, then by the same reasoning we have some subinterval $[a_{2},b_{2}]$ of $[a_{1},b_{1}]$ such that $\sup_{x\in[a_{2},b_{2}]}f(x)\leq\dfrac{1}{2}$.
Proceed in this way we have a decreasing chain $\{[a_{n},b_{n}]\}$ such that $\sup_{x\in[a_{n},b_{n}]}f(x)\leq\dfrac{1}{n}$.
Take $c\in\displaystyle\bigcap_{n=1}^{\infty}[a_{n},b_{n}]$, then $f(c)\leq\dfrac{1}{n}$ for all $n=1,2,...$, now taking $n\rightarrow\infty$, we have $f(c)=0$.


TITLE: How do you show whether the given is a Vector Space over $\mathbb R$?
QUESTION [2 upvotes]: I'm stuck on a HW problem for my Linear Algebra class.
The problem is the following:
If the set is a vector space over $\mathbb R$, write true and explain why each of the following ten properties hold. If the set is not a vector space over $\mathbb R$, write false and identify all of the properties I-X which do not hold.

(a) $\{(x, y) ∈ \mathbb R^2 \:|\: 3x + 2y = 0 \}$ over $\mathbb R$ with the usual definitions of vector addition and scalar multiplication in $\mathbb R^2$

Now, I know what Vector Space over $\mathbb R$ is. I understand the question. There are 10 conditions that I must prove in order to prove that the given is a Vector Space over $\mathbb R$.
I just don't know where to begin. I understand that if for every $x,y$ in $V$, if $x+y$ exists in $V$, then one of the ten conditions is satisfied. How do I approach this with $3x + 2y = 0$?
A better question is what the statement $\{(x, y) ∈ \mathbb R^2 \:|\: 3x + 2y = 0 \}$ means. I understand it's all the $x$ and $y$ pairs which satisfy $3x + 2y = 0$, but am I supposed to break the $\mathbb R$ set in all of the possible combinations? For instance, $x = -2$, and $y = 3$ satisfies the function, but $x = 1$, $y = 1$ doesn't. So I certainly can't say that for every $x,y$ in $V$, $3x + 2y$ is in $V$.
I don't know where to begin proving. If I can only get a start somewhere, I would be able to do handle these problems well as I have a general knowledge of what to do, just not how to begin.
Thanks
Edit 1: Updated the question so it's easy to understand what it is asking.

REPLY [1 votes]: Consider an element of this set, the element satisfies two conditions. The first is that it must be an element of $\mathbb{R}^2$ and the second is that the components of this vector must satisfy
$$ ax + by = 0 $$
However these two conditions can be rephrased into something clearer. If we were to solve $y$, so the second component of the vector, from the above equation we would find that
$$y = - \frac{a}{b}x$$
So the first condition we stated, namely that the element must be in $\mathbb{R}^2$ is too broad, as there is a fixed condition for what the second component of the vector can be! From these observations we can show the following equality
$$ \{ (x,y) \in \mathbb{R}^2 : ax + by = 0\} = \{ (x, -\frac{a}{b}x) : x \in \mathbb{R}\}$$
As can be seen the second component of the vector is tied to the first component by the relation we derived above. Now the axioms we are interested in showing are considerably easier!
Using the above definition of the set I'll prove that the set is closed under addition. Consider any two elements of this set. The element will be of the form
$$ (v, - \frac{3}{2}v), \ (t,  - \frac{3}{2}t)$$
for some arbitrary $v,t \in \mathbb{R}$. Now consider the sum of these two elements
$$ (v, - \frac{3}{2}v) + (t,  - \frac{3}{2}t) = (v + t, -\frac{3}{2}(v + t))$$
Well $v + t \in \mathbb{R}$ so if we denote $u = v + t$ then the sum of these two vectors gives us a vector
$$ (u, - \frac{3}{2}u)$$
and if you look at the definition of the set above, this element must belong to the set!
Can you take it from here?


TITLE: For every $0<x<1$, is it possible to find a number $p>0$ such that $x=\frac{1}{1+p}$ or squeezed between two such fractions?
QUESTION [0 upvotes]: It sounds like true. I am trying to find a rigorous proof. I will post it here if I can find one. Any hint will be appreciated.

REPLY [2 votes]: Yes.  Fix $x \in (0,1)$.  Let $p = \dfrac{1-x}{x}$.  This satisfies $x = \dfrac{1}{1+p}$.  And this choice of $p$ is ok because $0 < x < 1$, i.e., $x \ne 0$.

REPLY [0 votes]: Hint (based on the original question, where "squeezed between fractions" suggested that $p$ must be an integer): The sequence $1/2, 1/3, 1/4, \ldots$ decreases monotonically to its limit $0$. What does the claim say about (for examples) $3/4$ and $1/\pi$?


text:
\begin{document}

\title{Homomorphic images of affine quandles}

\author{P\v remysl Jedli\v cka}
\author{David Stanovsk\'y}

\address{(P.J.) Department of Mathematics, Faculty of Engineering, Czech University of Life Sciences, Kam\'yck\'a 129, 16521 Praha 6, Czech Republic}
\address{(D.S.) Department of Algebra, Faculty of Mathematics and Physics, Charles University, Sokolovsk\'a 83, 18675 Praha 8, Czech Republic}

\email{(P.J.) jedlickap@tf.czu.cz}
\email{(D.S.) stanovsk@karlin.mff.cuni.cz}

\thanks{The second author was partly supported by the GA\v CR grant 13-01832S}

\keywords{Quandle, medial quandle, abelian quandle, quandle quotients.}

\subjclass[2010]{20N02, 15A78, 57M27.}
\date{\today}

\begin{abstract}
We are interested in abstract conditions that characterize homomorphic images of affine quandles. Our main result is a two-fold characterization of this class: one by a property of the displacement group, the other one by a property of the corresponding affine mesh. As a consequence, we obtain efficient algorithms for recognizing homomorphic images of affine quandles, including an efficient explicit construction of the covering affine quandle.
\end{abstract}

\maketitle

\section{Introduction}

Quandles are self-distributive structures that appear naturally in the context of knots, braids and in many other situations \cite{EN}.
Affine quandles (also called Alexander quandles) play a prominent role in quandle theory. From the algebraic perspective, they constitute an important building block \cite{AG,BS,JPSZ}, and it has been observed that many small connected quandles are affine \cite{ESG,G}. In knot theory, there is a close connection between the Alexander invariant and coloring by affine quandles \cite{Bae,Joy}.

In the present paper, we focus on quandles that are \emph{homomorphic images} (or quotients) \emph{of} affine quandles. The paper is, in a way, a blueprint of our recent writeup \cite{JPSZ-qa} on quandles that \emph{embed into} affine quandles. The similarities and differences are outlined below, and explained in detail in Section \ref{sec:main}.

Affine quandles are medial, and so are their subquandles and homomorphic images. Therefore, one can use the representation developed in \cite{JPSZ}, where medial quandles are described using certain heterogeneous affine structures, called affine meshes. For both classes, we have a two-fold characterization (Theorems \ref{thm:embed_affine} and Theorem \ref{thm:homim_affine}): one by a property of the displacement group, the other one by a property of the corresponding affine mesh.

In both cases, the characterizing conditions are both algorithmically efficient and fairly easy to check for concrete small examples, given either by a mesh, or by a multiplication table. In both proofs, the hard step is, to find an affine quandle such that a given quandle embeds into, resp. projects onto, it. There is, however, one significant difference: for embeddings, our proof is not constructive and we do not know an efficient way to construct such an affine quandle; for quotients, our proof is constructive and turns into a polynomial-time algorithm that constructs the affine quandle.

The two characterization theorems, and several examples illustrating the similarities and differences, are formulated in Section~\ref{sec:main}.
The final Section \ref{sec:proof} contains the proof of the main theorem and an explicit statement of the algorithms based on the proof.

\section{Preliminaries} \label{sec:terminology}

\subsection{Quandles}

For a general introduction to quandle theory we refer to \cite{AG,EN}. The proofs of all statements in this subsection can be found in the introductory part of \cite{HSV} (and also elsewhere, in various notation systems).

We will write mappings acting on the left, hence conjugation in groups will be denoted by $x^y=yxy^{-1}$, and consequently, the commutator will be defined as $[x,y]=y^xy^{-1}=xyx^{-1}y^{-1}$.

A \emph{quandle} is an algebraic structure $(Q,*)$ which is \emph{idempotent} (it satisfies the identity $x*x=x$) and in which all left translations, $L_x(y)=x*y$, are automorphisms.
The unique $y$ such that $x*y=z$ will be denoted $y=x\ld z$. There are two important permutation groups associated to every quandle:
the (left) \emph{multiplication group}, generated by all left translations,
\[\lmlt Q=\langle L_a:\ a\in Q\rangle\leq\aut Q,\]
and its subgroup, the \emph{displacement group}, defined by
\[\dis Q=\langle L_aL_b^{-1}:\ a,b\in Q\rangle\leq\lmlt Q.\]

It is easy to see that $\dis Q=\langle L_aL_e^{-1}:\ a\in Q\rangle$ for any fixed $e\in Q$.
Both groups have the same orbits of the natural action on $Q$, to be called \emph{orbits} of the quandle $Q$, and denoted
\[Qe=\{\alpha(e):\ \alpha\in\lmlt Q\}=\{\alpha(e):\ \alpha\in\dis Q\}.\]
Orbits are subquandles of $Q$. They form a block system, to be called the \emph{orbit decomposition} of $Q$.

Observe that $L_{\alpha(x)}=(L_x)^\alpha$ for every automorphism $\alpha$. Consequently, both $\lmlt Q$ and $\dis Q$ are normal in $\aut Q$.

Let $\lambda=\{(a,b):L_a=L_b\}$ denote the \emph{Cayley kernel} of a quandle $Q$. This is always a congruence on $Q$, since it is the kernel of the quandle homomorphism $a\mapsto L_a$ from $Q$ into the symmetric group $S_Q$ under the conjugation operation.

A quandle is called \emph{medial} if it satisfies the identity $(x*y)*(u*v)=(x*u)*(y*v)$.

A quandle is medial if and only if its displacement group is abelian.

Let $(A,+)$ be an abelian group, $f$ its automorphism, and define an operation on the set $A$ by
\[a*b=(1-f)(a)+f(b).\]
Then $(A,*)$ is a medial quandle, to be denoted $\aff{A,f}$, and called \emph{affine} over the group $(A,+)$.
Here $1$ refers to the identity mapping, hence $g=1-f$ is the mapping $g(x)=x-f(x)$.

Let $Q=\aff{A,f}$. Then $\dis Q\simeq\im{1-f}$, where $a\in\im{1-f}$ corresponds to the mapping $x\mapsto a+x$ (indeed, $L_aL_b^{-1}(x)=(1-f)(a-b)+x$).
Hence, the orbits of $Q$ are the cosets of $\im{1-f}$.

\subsection{Affine meshes}

In \cite{JPSZ}, we developed a representation of medial quandles by affine meshes.
Here we recall the essential constructions and results.

\begin{de}
An \emph{affine mesh} over a non-empty set $I$ is a triple
$$\mathcal A=((A_i)_{i\in I};\,(\varphi_{i,j})_{i,j\in I};\,(c_{i,j})_{i,j\in I})$$ where $A_i$ are abelian groups, $\varphi_{i,j}:A_i\to A_j$ homomorphisms, and $c_{i,j}\in A_j$ constants, satisfying the following conditions, for every $i,j,j',k\in I$:
\begin{enumerate}
    \item[(M1)] $1-\varphi_{i,i}$ is an automorphism of $A_i$;
    \item[(M2)] $c_{i,i}=0$;
    \item[(M3)] $\varphi_{j,k}\varphi_{i,j}=\varphi_{j',k}\varphi_{i,j'}$, i.e., the following diagram commutes:
$$\begin{CD}
A_i @>\varphi_{i,j}>> A_j\\ @VV\varphi_{i,j'}V @VV\varphi_{j,k}V\\
A_{j'} @>\varphi_{j',k}>> A_k
\end{CD}$$
    \item[(M4)] $\varphi_{j,k}(c_{i,j})=\varphi_{k,k}(c_{i,k}-c_{j,k})$.
\end{enumerate}
The mesh is called \emph{indecomposable} if,

for every $j\in I$, the group $A_j$ is generated by all the elements $c_{i,j}$, $\varphi_{i,j}(a)$ with $i\in I$ and $a\in A_i$.
\end{de}

If the index set is clear from the context, we shall write briefly $\mathcal A=(A_i;\varphi_{i,j};c_{i,j})$.

\begin{de}
The \emph{sum of an affine mesh} $(A_i;\varphi_{i,j};c_{i,j})$ is an algebraic structure $(A,*)$ defined on the disjoint union of the sets $A_i$ by
\[ a\ast b=c_{i,j}+\varphi_{i,j}(a)+(1-\varphi_{j,j})(b). \]
for every $a\in A_i$ and $b\in A_j$.
\end{de}

The sum of any affine mesh is a medial quandle, with $a\ld b=(1-\varphi_{j,j})^{-1}(b-\varphi_{i,j}(a)-c_{i,j})$.
The fibers $A_i$ form subquandles which are affine, namely, $\aff{A_i,1-\varphi_{i,i}}$.
If the mesh is indecomposable, the fibers coincide with the orbits.

\begin{theorem}\cite{JPSZ}\label{thm:decomposition}
A binary algebraic structure is a medial quandle if and only if it is the sum of an indecomposable affine mesh.
\end{theorem}

\section{The two characterization theorems}\label{sec:main}

The key to recognition of quandles that embed into an affine quandle is the \emph{lack of fixed points} (i.e., semiregularity) in the displacement group, which translates into a certain form of homogenity of the underlying meshes. The following is a reformulation of the main result of \cite{JPSZ-qa} (the special type of meshes in condition (3) was called a \emph{semiregular extension}).

\begin{theorem}\cite{JPSZ-qa}\label{thm:embed_affine}
The following statements are equivalent for a quandle $Q$:
\begin{enumerate}
	\item $Q$ embeds into an affine quandle;
	\item $\dis Q$ is abelian and semiregular;
	\item there is an abelian group $A$, an automorphism $\psi$ of $A$ and elements $d_i\in A$ such that
	$Q$ is isomorphic to the sum of an affine mesh $((A_i);(\varphi_{i,j});(c_{i,j}))$ where $A_i=A$ for every $i$, and $\varphi_{i,j}=1-\psi$ and $c_{i,j}=d_i-d_j$ for every $i,j\in I$.

\end{enumerate}
\end{theorem}

Given a multiplication table of a quandle $Q$, it is easy to verify condition (2). Given an affine mesh, it is easy to verify condition (3). However, in either case, we do not know how to find efficiently an abelian group $A$ and its automorphism $f$ such that $Q$ embeds into $\aff{A,f}$.

The key to recognition of quandles that are quotients of affine quandles is the \emph{size} of the displacement group, which translates into a certain form of linearity of the underlying meshes.

\begin{de}
We will say that a quandle $Q$ has a \emph{tiny displacement group} if, for some $e\in Q$, \[ \dis Q=\{L_xL_e^{-1}:x\in Q\}. \]
\end{de}

Note that if $\dis Q$ is tiny, then $\dis Q=\{L_xL_f^{-1}:x\in Q\}$ for \emph{every} $f\in Q$: to express $L_xL_e^{-1}$ as $L_yL_f^{-1}$ for some $y$, consider $L_xL_e^{-1}L_fL_e^{-1}\in\dis Q$ and take $y$ such that it equals $L_yL_e^{-1}$.

The following is the main result of the present paper.

\begin{theorem}\label{thm:homim_affine}
The following statements are equivalent for a quandle $Q$:
\begin{enumerate}
	\item $Q$ is a homomorphic image of an affine quandle;
	\item $\dis Q$ is abelian and tiny;
	\item $Q$ is the sum of an affine mesh $((A_i);(\varphi_{i,j});(c_{i,j}))$ such that
	$$\{ (\varphi_{i,j}(a)+c_{i,j})_{j\in I}:\ i\in I,\, a\in A_i\}\subseteq\prod_{j\in I} A_j$$
	is a coset of a subgroup of $\prod A_j$.

\end{enumerate}
\end{theorem}

Given a multiplication table of a quandle $Q$, it is easy to verify condition (2). Given an affine mesh, it is easy to verify condition (3) (a subset $X$ of a group $G$ is a coset if and only if, for any $h\in X$, $-h+X$ is a subgroup of $G$). As we shall see in the next section, the proof of Theorem \ref{thm:homim_affine} provides an efficient algorithm that constructs an abelian group $A$ and its automorphism $f$ such that $\aff{A,f}$ maps homomorphically onto $Q$.

Condition (3) is particularly easy to use for 2-reductive medial quandles, i.e., quandles given by meshes with $\varphi_{i,j}=0$ for all $i,j$ \cite[Section 6]{JPSZ}. Indeed, the sum of a mesh $(A_i,0,(c_{i,j}))$ is a homomorphic image of an affine quandle if and only if the rows of the matrix $(c_{i,j})$ form a coset in the group $\prod A_j$.

\begin{example}
All of the following properties are easy to verify using conditions (3) in Theorems \ref{thm:embed_affine} and \ref{thm:homim_affine}.
\begin{itemize}
	\item The sum of the affine mesh \[ \left((\Z_2,\Z_2,\Z_2);\ \left( \begin{smallmatrix} 0 & 0 & 0\\ 0 & 0 & 0 \\ 0 & 0 & 0\end{smallmatrix}\right);\ \left(\begin{smallmatrix} 0&0&1\\0&0&1\\1&1&0\end{smallmatrix}\right)\right) \]
	both embeds into an affine quandle (for instance into $\aff{\Z_8,5}$ as $\{0,4,2,6,1,5\}$), and it is a homomorphic image of an affine quandle (for example of
	$\aff{\Z_8,5}$ over the congruence $\{0\},\{2\},\{4\},\{6\},\{1,3\},\{5,7\}$). However, it is not affine, since it has three orbits, unlike any of the two 6-element affine quandles.
	\item The sum of the affine mesh \[ \left((\Z_3,\Z_3);\ \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0\end{smallmatrix}\right);\ \left(\begin{smallmatrix} 0&1\\1&0\end{smallmatrix}\right)\right) \]
	embeds into an affine quandle (for instance into $\aff{\Z_9,4}$ as $\{0,3,6,1,4,7\}$), but it is not a homomorphic image of an affine quandle.
	\item The sum of the affine mesh \[ \left((\Z_2,\Z_1);\ \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0\end{smallmatrix}\right);\ \left(\begin{smallmatrix} 0&0\\1&0\end{smallmatrix}\right)\right) \]
	is a homomorphic image of an affine quandle (for example of $\aff{\Z_4,-1}$ over the congruence $\{0\},\{2\},\{1,3\}$), but does not embed into an affine quandle since
	it has orbits of different sizes.
\end{itemize}
\end{example}

\begin{example}
 We calculate all 2-reductive quandles with two orbits that are homomorphic images of affine quandles. Such quandles are sums of indecomposable affine meshes of type
 \[\left( (A,B);\ \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0\end{smallmatrix}\right);\ \left( \begin{smallmatrix} 0 & b \\ a & 0\end{smallmatrix}\right) \right)\]
where $A=\langle a\rangle$ and $B=\langle b\rangle$. Condition (3) of Theorem \ref{thm:homim_affine} states that the rows of the matrix~$(c_{i,j})$ form a coset in $A\times B$. The coset is necessarily $(a,0)+\langle(-a,b)\rangle$, hence $2a=2b=0$, $A,B\in\{\Z_1,\Z_2\}$ and there are only three options, up to isomorphism:
 \[
 \left( (\Z_1,\Z_1);\ \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0\end{smallmatrix}\right)
 ;\ \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0\end{smallmatrix}\right) \right), \qquad
 \left( (\Z_2,\Z_1);\ \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0\end{smallmatrix}\right)
 ;\ \left( \begin{smallmatrix} 0 & 0 \\ 1 & 0\end{smallmatrix}\right) \right), \quad
 \left( (\Z_2,\Z_2);\ \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0\end{smallmatrix}\right)
 ;\ \left( \begin{smallmatrix} 0 & 1 \\ 1 & 0\end{smallmatrix}\right) \right).\]
\end{example}

\section{The proof and the algorithm}\label{sec:proof}

Informally, a \emph{multiset} is a generalization of the notion of a set where elements can repeat. Tuples can be considered as multisets, forgetting the indexing. A \emph{multitransversal} for a block system is a multiset which takes the same amount of elements from each block (i.e., a multiset $T$ such that $|T\cap B_1|=|T\cap B_2|$, for every pair of blocks $B_1,B_2$).
The {\em multiplicity} of a multitransversal is
the cardinality of each such $T\cap B_i$.

\begin{proof}[Proof of Theorem \ref{thm:homim_affine}]
$(1)\Rightarrow(2)$ Affine quandles satisfy (2) and both properties carry over to homomorphic images.

$(2)\Rightarrow(1)$
We shall construct a group~$A$ and an automorphism~$f$ such that $\aff{A,f}$ maps homomorphically onto $Q$.
Let $T$ be a multitransversal to the Cayley kernel $\lambda=\{(a,b):L_a=L_b\}$ which contains at least one element from each orbit of $Q$ (take a transversal, add a representative of every orbit, and increase multiplicity of selected elements to obtain a multitransversal). Let $\kappa$ be the multiplicity of $T$.

We will treat the elements of~$T$ as formally different and construct an abelian group operation on~$T$. Choose an element~$e\in T$ which will play the role of zero.
Consider an arbitrary abelian group $K=(K,+,-,0)$ of order $\kappa$ and an arbitrary mapping $\nu:T\to K$ which is bijective on every block of $T^2\cap\lambda$ and satisfies $\nu(e)=0$.
Define an operation $\oplus$ on~$T$ by
\[a\oplus b=c\ \Leftrightarrow\ L_aL_e^{-1}L_b=L_c\text{ and }\nu(a)+\nu(b)=\nu(c).\]
The operation is well defined: $\alpha=L_aL_e^{-1}L_bL_e^{-1}$ is in $\dis Q$ which is tiny, hence there exists $c\in Q$ such that $\alpha=L_cL_e^{-1}$ and among the $\kappa$ candidates for $c$ in~$T$, there is a unique one with $\nu(c)=\nu(a)+\nu(b)$.

Clearly, $e$ is  a unit element for $\oplus$. An inverse to $a$ is an element $b$ such that $L_aL_e^{-1}L_b=L_e$ and $\nu(a)+\nu(b)=0$, that is, $b$ such that $L_bL_e^{-1}=(L_aL_e^{-1})^{-1}$ and $\nu(b)=-\nu(a)$; such $b$ exists because $\dis Q$ is tiny. The operation $\oplus$ is commutative because both $\dis Q$ and $K$ are abelian. It is associative, because $d=a\oplus(b\oplus c)$ if and only if $L_d=L_aL_e^{-1}L_{b\oplus c}=L_aL_e^{-1}L_bL_e^{-1}L_c$ and $\nu(d)=\nu(a)+\nu(b\oplus c)=\nu(a)+\nu(b)+\nu(c)$; the two rightmost expressions do not depend on the bracketing.

Now, let \[A=\dis{Q}\times(T,\oplus)\] and consider the mapping \[f:A\to A,\quad (\alpha,a)\mapsto(L_e\alpha L_a^{-1},a).\]
Then $f$ is an endomorphism of $A$, because
\begin{multline*}
f((\alpha,a))+f((\beta,b))=(L_e\alpha L_a^{-1},a)+(L_e\beta L_b^{-1},b)
=(L_e\alpha\beta L_a^{-1}L_eL_b^{-1},a\oplus b)=\\
=(L_e\alpha\beta L_e^{-1}(L_bL_e^{-1}L_aL_e^{-1})^{-1},a\oplus b)=
(L_e\alpha\beta L_e^{-1}(L_{b\oplus a}L_e^{-1})^{-1},a\oplus b)=f(\alpha\beta,a\oplus b).
\end{multline*}
The kernel of~$f$ is trivial: $\mathrm{Ker}(f)=\{(\alpha,a):L_e\alpha L_a^{-1}=1$ and $a=e\}=\{(1,e)\}$. To show that $f$ is onto, notice that $(\alpha,a)=f((L_e^{-1}\alpha L_a,a))$ where
$L_e^{-1}\alpha L_a=L_e^{-1}(\alpha L_aL_e^{-1})L_e\in\dis Q$ since it is normal in $\lmlt Q$. Hence $f$ is an automorphism of $A$.

Finally, consider \[\psi:\aff{A,f}\to Q,\quad (\alpha,a)\mapsto \alpha(a).\]
We have
\begin{align*}
\psi((\alpha,a)*(\beta,b))&=\psi((\alpha,a)f((\alpha,a))^{-1}f((\beta,b)))\\ &=\psi((\alpha L_a\alpha^{-1}L_e^{-1}L_e\beta L_b^{-1},b))=
\alpha L_a\alpha^{-1}\beta L_b^{-1}(b)=L_{\alpha(a)}\beta(b)=\alpha(a)*\beta(b),
\end{align*}
hence $\psi$ is a homomorphism. It is onto, because each orbit of $Q$ contains at least one element in $T$.

$(2)\Leftrightarrow(3)$
Assume that $Q$ is the sum of an affine mesh $((A_i);(\varphi_{i,j});(c_{i,j}))$. The displacement mapping $L_aL_b^{-1}$ with $a\in A_i$, $b\in A_j$ can be expressed as
\[L_aL_b^{-1}(x)=x+\varphi_{i,k}(a)-\varphi_{j,k}(b)+c_{i,k}-c_{j,k} \text{ whenever }x\in A_k. \]
We will prove that $\dis Q$ is tiny if and only if $\{ (\varphi_{i,k}(a)+c_{i,k})_{k\in I}:\ i\in I,\, a\in A_i\}$ is a coset in $\prod A_k$, that is, if and only if, for some $e\in A_j$, the set
\[ S_e=-(\varphi_{j,k}(e)+c_{j,k})_{k\in I}+\{ (\varphi_{i,k}(a)+c_{i,k})_{k\in I}:\ i\in I,\, a\in A_i\} \] is a subgroup of $\prod A_k$.

Fix $e\in A_j$. Then the set $\Lambda_e=\{L_aL_e^{-1}:a\in Q\}$	is in 1-1 correspondence with the set $S_e$, where $L_aL_e^{-1}$ corresponds to the tuple $=(-\varphi_{j,k}(e)-c_{j,k}+\varphi_{i,k}(a)+c_{i,k})_{k\in I}$. Moreover, composition of mappings from $\Lambda_e$ corresponds to addition of the corresponding elements of $S_e$. Therefore, $\Lambda_e$ is closed with respect to composition and inversion if and only if $S_e$ is closed with respect to addition and subtraction.

Consequently, $\dis Q$ is tiny if and only if $\dis Q=\Lambda_e$ for some $e$, which is equivalent to $S_e\leq\prod A_k$.
\end{proof}

\def\krok#1#2{#1 & #2 \\}
\def\io#1#2{{$\ $}\\ \begin{tabular}{ll} {\bf In:} & #1 \\ {\bf Out:} & #2 \end{tabular} \\}
\def\afont#1{{\bf #1}}

From an algorithmic point of view, the size of the multitransversal $T$ is important. Indeed, $|T|=|Q/\lambda|\cdot\kappa$, and we can always take $\kappa$ at most the number of orbits. Both values are bounded by the size of $Q$, hence we can always find $T$ such that $|T|\leq |Q|^2$. The following example shows that there is also a quadratic lower bound.

\begin{example}\label{ex:max_quandle}
Let $n,k$ be natural numbers such that $2^k<n$. Consider the affine mesh $\mathcal A_{n,k}=(Z;0;C)$ where
$Z=(\Z_2,\dots,\Z_2,\Z_1,\dots,\Z_1)$ contains $k$ copies of $\Z_2$ and $n-k$ copies of $\Z_1$, $0$ is the matrix of zero homomorphisms, and
\[ C=\left(\begin{array}{c|c}
D & 0 \\ \hline
0 & 0
\end{array}\right) \]
where $D$ is an arbitrary $2^k\times k$ matrix over $\Z_2$ whose set of row vectors equals $\Z_2^k$. To simplify notation, assume that the zero vector is in the last row.

Clearly, $\mathcal A_{n,k}$ is an indecomposable affine mesh and using Theorem~\ref{thm:homim_affine}, we see that its sum, $Q$, is a homomorphic image of an affine quandle.
The quandle $Q$ has $n$ orbits and $|Q|=n+k$.

Observe that the Cayley kernel of $Q$ consists of all pairs $(a,b)$ where $a$ is in the $i$-th orbit, $b$ is in the $j$-th orbit, and the $i$-th and $j$-th row in $C$ are equal.
Therefore, $\lambda$ has $2^k$ blocks. Most of them have 1 or 2 elements, and there is one large block $B$ of size $n-2^k+1$, consisting of singleton orbits with indices $2^k,\dots,n$.
Consequently, any multitransversal $T$ intersectiong all orbits must choose all elements from $B$, thus its multiplicity $\kappa$ must be at least $n-2^k+1$ and we get
\[ |T|\geq|Q/\lambda|\cdot\kappa=2^k\cdot(n-2^k+1) \]
(the lower bound can be achieved). In particular, if $n=2^{k+1}$, we have $|T|\geq\frac n2\cdot(\frac n2+1)\approx|Q|^2/4$.
\end{example}

In the rest of the section, we present two algorithms.
The input is a finite quandle, in any form that allows efficient calculation of left translations (for example, the multiplication table, or the corresponding affine mesh).
In the first one, we are asked to decide whether it is a homomorphic image of an affine quandle. In the second one, we are asked to find such an affine quandle.

\begin{algorithm}\label{alg:homim-affine}
\noindent
\io{a finite quandle $Q$}{is $Q$ a homomorphic image of an affine quandle?}
\begin{tabular}{ll}
\krok{1.}{pick $e\in Q$ }
\krok{2.}{$D:=\{L_xL_e^{-1}:x\in Q\}$}
\krok{3.}{\afont{for each} $\alpha,\beta\in D$ \afont{do}}
\krok{4.}{\quad \afont{if} $\alpha\beta\neq\beta\alpha$ or $\alpha\beta\not\in D$ \afont{then return} false}
\krok{5.}{\afont{return} true}
\end{tabular}
\end{algorithm}

On line 2, we define the group $\dis Q$. On lines 3 and 4, we verify condition (2) of Theorem \ref{thm:homim_affine}: if we find a non-commuting pair, or if we find a pair whose composition is not inside $D$, the algorithm reports a failure.

\begin{proposition}\label{p:alg-homim-affine}
Algorithm \ref{alg:homim-affine} runs in a polynomial time with respect to $n=|Q|$, namely $\bigo(n^4\log n)$ (i.e., in a quadratic time with respect to the input size).
\end{proposition}

\begin{proof}
All operations performed with permutations on $Q$ (comparison, composition) can be calculated in $\bigo(n\log n)$ time. The set $D$ has at most $n$ elements, hence the loop on lines 3--5 performs at most $n^2$ steps. Checking commutativity takes $\bigo(n\log n)$ time (two compositions, one comparison), checking containment in $D$ takes $\bigo(n^2\log n)$ time (one composition, at most $n$ comparisons).
\end{proof}

\begin{algorithm}\label{alg:homim-affine2}
\noindent
\io{a finite quandle $Q$}{$(A,f)$ such that $Q\simeq\aff{A,f}$, or failure if such $(A,f)$ does not exist}
\begin{tabular}{ll}
\krok{1.}{pick $e\in Q$ }
\krok{2.}{$D:=\{L_xL_e^{-1}:x\in Q\}=\{\alpha_0,\dots,\alpha_{m-1}\}$ where $\alpha_0=1$}
\krok{3.}{\afont{for each} $\alpha,\beta\in D$ \afont{do}}
\krok{4.}{\quad \afont{if} $\alpha\beta\neq\beta\alpha$ or $\alpha\beta\not\in D$ \afont{then stop} with failure}
\krok{5.}{\afont{for each} $0\leq i<m$ \afont{do}}
\krok{6.}{\quad find all $x_{i,0},\dots,x_{i,k_i-1}$ such that $L_{x_{i,j}}L_e^{-1}=\alpha_i$ (for $i=0$, take $x_{0,0}=e$)}
\krok{7.}{$\kappa:=\max\{k_i\}$}
\krok{8.}{\afont{for each} $0\leq i<m$ and $0\leq j < \kappa$ \afont{do}}
\krok{9.}{\quad $T_{i\cdot \kappa +j}:=x_{i,j \bmod k_i}$}
\krok{10.}{\afont{for each} $0\leq i,i'<m$ and $0\leq j,j'<\kappa$ \afont{do}}
\krok{11.}{\quad set $T_{i\cdot \kappa+j}\oplus T_{i'\cdot\kappa+j'}:=T_{i''\cdot\kappa+((j+j')\bmod \kappa)}$ such that $L_{x_{i'',0}}L_e^{-1}=L_{x_{i,0}}L_e^{-1}L_{x_{i',0}}L_e^{-1}$}
\krok{12.}{\afont{return} $(D\times T,f)$ where $f(\alpha,T_{i\cdot\kappa+j})=(L_e\alpha L_{x_{i,j}}^{-1},T_{i\cdot\kappa+j})$}
\end{tabular}
\end{algorithm}

On lines 5 and 6 we calculate the blocks of the Cayley kernel $\lambda$.
To keep things simple and to avoid calculation of the orbits of $Q$, we put every element of~$Q$ in~$T$ (occasionally several times).
We implicitly choose the group~$K$ to be the cyclic group $\Z_\kappa$. The construction of the group $(T,\oplus)$ with $T=\{T_k:k=0,\dots,m\kappa-1\}$ on lines 10 and 11 follows the proof of Theorem \ref{thm:homim_affine}.

\begin{proposition}\label{p:alg-homim-affine2}
Algorithm \ref{alg:homim-affine2} runs in a polynomial time with respect to $n=|Q|$, namely $\bigo(n^6\log n)$ (i.e., in a cubic time with respect to the input size).
\end{proposition}

\begin{proof}
The most costly part is the cycle on lines 10 and 11 requiring $m^2\kappa^2$ steps, each of complexity $m\cdot n\log n$
(search for a permutation in a list of length $m$). In the worst case, we have to assume both $m,\kappa=\Theta(n)$.
\end{proof}

Our choice of $T$ is simple, but often not optimal in terms of size. Here we outline a better approach.
First, construct a subset $S\subseteq Q$ which is a transversal of the orbit decomposition, and minimizes the maximal number of elements taken from any single block of $\lambda$; shortly,  \[\min_S \max_{B\in Q/\lambda} |B\cap S|. \]
Given $S$, we obtain $T$ by adding a proper amount of arbitrarily chosen elements from each block of $\lambda$. Finding the optimal set $S$ can be formulated as an instance of integer linear programming. Let $A_1,\dots,A_n$ be the orbits of $Q$, and $B_1,\dots,B_m$ the blocks of $\lambda$. Let $x_{i,j}$ be the indeterminates that tell how many elements we choose from $A_i\cap B_j$. We set $x_{i,j}=0$ whenever the two sets are disjoint. The constraints are $x_{i,j}\geq 0$ and $\sum_{j=1}^m x_{i,j}=1$ for every $i=1,\dots,n$ (thus we choose exactly one element from each $A_i$). We minimize $c$ such that $\sum_{i=1}^n x_{i,j}\leq c$ for every $j=1,\dots,m$.
While integer linear programming is a difficult problem in general, there are efficient heuristics for finding good solutions.

For the quandle from Example \ref{ex:max_quandle}, our choice of $T$ is optimal. Therefore, the worst case asymptotic complexity of our algorithm cannot be improved by a better choice of $T$.

\begin{remark}
In \cite{JPSZ-qa} we described an efficient algorithm to recognize quandles isomorphic to affine quandles, but we do not know how to find efficiently the actual affine representation (i.e., the group and its automorphism).
The construction from the proof of Theorem \ref{thm:homim_affine} does not help either. The homomorphism $\psi:\aff{A,f}\to Q$ constructed in the proof is bijective if and only if the multitransversal $T$ has precisely one element from each orbit of $Q$. However, many affine quandles do not admit such $T$: for example, every affine latin quandle $Q$ has only one orbit, but $|T|\geq|Q|$.
\end{remark}

\subsection*{Acknowledgement}
The authors wish to dedicate the paper to memory
of Patrick Dehornoy who was one of the most inspiring
guides through the world of self-distributivity.


TITLE: Multiplying magic squares like matrices to hopefully arrive at another magic square
QUESTION [1 upvotes]: Well, the title actually describes what is the problem in question. I was just thinking a bit about magic squares and this question popped-up. It could be that it is not interesting but I do not see a reason why it should not be asked.
Suppose that we have two magic squares of the same order $n>2$.
We can view those two magic squares as matrices and we can multiply them as we multiply matrices in the usual way.
The question is:

Is it true that for every natural number $n>2$ there exist two magic squares $M_1$ and $M_2$ such that either their product $M_1M_2$ or the product $M_2M_1$ (viewed as the product of matrices) is a magic square?

I really do not know can the way in which we multiply matrices give birth to another magic square constructed by multiplying two magic squares as matrices, your ideas are welcomed.
Also, suppose that all entries in magic squares are different.

REPLY [4 votes]: Two squares with the magic sum of 2 can be multiplied together to get 2 times a square with the magic sum of 2.  The first two squares have consecutive entries.  All squares have no internal repetition.


TITLE: Finite double summation - the upper limit of the inner summation depends on the outer summation's parameter
QUESTION [2 upvotes]: I am doing some work on finding the distribution of a sum of two independent random variables. In my actual work these two variables are independent, yet have a very different distribution.
I wanted to treat an example case, but I lack the knowledge of double summations. Before starting the example, let me say that I fully know how to obtain the cumulative distribution function in a number of ways, so this question is purely on how to compute double summations of the kind I find in the following example.
Thanks in advance.

Let $X_1 \sim geom(p_1)$, $X_2 \sim geom(p_2)$, both with support $\{1,2,\ldots\}$ and $Y = X_1 + X_2$.
I want to compute the cumulative distribution function of $Y$, using the following approach,
\begin{align}
\mathbb{P}(Y \leq k) &= \sum_{j = 1}^{k-1} \sum_{i=1}^{k-j} \mathbb{P}(X_1=i)\mathbb{P}(X_2=j) \\
&= \sum_{j = 1}^{k-1} \sum_{i=1}^{k-j} p_1(1-p_1)^{i-1} p_2(1-p_2)^{j-1}.
\end{align}
Here is where I get stuck. How to compute the above double summation? I know, using Mathematica to evaluate the double summation, that the answer should be
\begin{align}
\mathbb{P}(Y \leq k) &= \frac{p_1-p_1(1-p_2)^k+p_2((1-p_1)^k-1)}{p_1-p_2},
\end{align}
which is indeed correct when compared to e.g. a generalized negative binomial distribution with correct parameters.

REPLY [0 votes]: If all you need is a decent approximation using a stratified sampling Monte Carlo approach:

Generate a table of values for the percentiles 0.5%, 1.5%,...,99.5% for each distribution (a finer mesh could be used for more accurate results)
Calculate all possible sums (or any other function of the two random variables)
Sort the values smallest to largest, count the n results (i.e. 10,000 for example in line 1), then assign percentiles 1/2n, 3/2n,..., (2n-1)/2n