text:
\begin{document}

\begin{frontmatter}

\title{Guo's index for some classes of matrices}

\author{Mar\'{i}a Robbiano}

\address{Departamento de Matem\'{a}ticas, Facultad de Ciencias. Universidad Cat\'{o}lica del Norte. Av. Angamos 0610 Antofagasta, Chile.}
\ead{mrobbiano@ucn.cl}

\begin{abstract}

\noindent A permutative matrix is a square matrix such that every row is a permutation of the first row. A circulant matrix is a matrix where each row is a cyclic shift of the row above to the right.
The Guo's index $\lambda_0$ of a realizable list is the minimum spectral radius such that the list (up to the initial spectral radius) together with $\lambda_0$
is realizable.
The Guo's index of some permutative matrices is obtained. Our results are constructive. Some examples designed using MATLAB are given at the end of the paper.
\end{abstract}

\begin{keyword}
Inverse eigenvalue problem; Structured inverse eigenvalue problem; Circulant matrix; Permutative matrix; Guo index
\MSC 15A18, 15A29, 15B99.
\end{keyword}

\end{frontmatter}
\section{Preliminaries}
\noindent In this section we present a brief resume.  Recall that a square matrix $A=(a_{ij})$ is nonnegative ($A \geq 0$) if and only if $a_{ij} \geq 0$ \  $ \left( 1\leq i,j\leq n\right).$
A list is an $n$-tuple, $\Lambda =\left(\lambda_1,\ldots,\lambda_n\right)$ of complex numbers and it is \textit{realized} by a $n$-by $n$ nonnegative matrix $A$ if the set formed its components and the spectrum of $A$ (considering multiplicities) coincide.
The NIEP is the problem of determining necessary and sufficient conditions for a list of $n$ complex
numbers to be realized by an $n$-by-$n$ nonnegative matrix $A$. If a list $\Lambda$ is realized by a nonnegative matrix $A$, then $\Lambda$ is \textit{realizable} and the matrix $A$ \textit{realizes} $\Lambda$ (or, that is a  \textit{realizing matrix} for the list). Some results can be seen in e.g. \cite{Laffey1,Laffey2,Laffey-Smigoc}.
 A variant of the original problem is the question for which lists of $n$ real numbers can occur as eigenvalues of an $n$-by-$n$  nonnegative matrix and it is called real nonnegative inverse eigenvalue problem (RNIEP). Some results can be seen in e.g. \cite{Laffey}. The structured NIEP is an analogous problem to NIEP where the realizing matrix must be structured, for instance, the matrix can be symmetric, Toeplitz, Hankel, circulant, normal, permutative, etc., see in \cite{Fiedler, Laffey, LMc, MAR,PP} and the reference therein.
 In this paper we deal with structured matrices. In particular, permutative and circulant matrices.

\noindent Throughout the text, $\sigma\left(A\right)$  denotes the set of eigenvalues of a square matrix $A$. As usual, the identity matrix of order $n$ is denoted by $I_n$ and if the order of the identity matrix can be easily deduced then it is just denoted by $I$.

\noindent Since a nonnegative matrix is real, its characteristic polynomial must have real coefficients and then
$ \{\lambda_{0}, \ldots, \lambda_{n-1}\} =\Lambda= \overline{\Lambda} =  \{\overline{\lambda_{0}}, \ldots, \overline{\lambda_{n-1}}\},$ where $\overline{\lambda}$ stands for the complex conjugate of $\lambda \in \mathbb{C}.$

\noindent Therefore consider the following definition:

\begin{definition}
The complex $n$-tuple $(\lambda_{0},\ldots,\lambda_{n-1})$ is  \textit{closed under complex conjugation} if the condition $$\{\lambda_{0},\ldots,\lambda_{n-1}\}=\{\overline{\lambda_{0}},\ldots,\overline{\lambda_{n-1}}\},$$ holds.
\end{definition}

\noindent The Perron-Frobenius theory of nonnegative matrices \cite{Berman} plays in this problem an important role.
The theory provides several important necessary conditions for the NIEP. See below some of these conditions resumed. Here, for $1\leq k \leq n,$ \ $s_{k} (\Lambda)=\sum\limits_{i=0}^{n-1}\lambda
_{i}^{k}$ is named the $k$-th moment.

\noindent Some necessary conditions for the list  $\Lambda = (\lambda_{0}, \ldots, \lambda_{n-1})$ of complex numbers to be the spectrum of a nonnegative matrix are:
\begin{enumerate}
\item The spectral radius,  $\max \left\{ \left\vert \lambda \right\vert
:\lambda \in \Lambda \right\} $, called the Perron eigenvalue,  belongs to $\Lambda.$

\item The list $\Lambda $ is closed under complex conjugation.

\item $s_{k}\left(\Lambda \right)\geq 0,$ \ $ k \geq 1 $.

\item $s_{k}^{m}\left( \Lambda \right) \leq n^{m-1}s_{km}\left( \Lambda
\right),$ \ $ k \geq 1 $.
\end{enumerate}
 The last condition was
proved by Johnson \cite{Johnson} and independently by Loewy and London \cite{LwyLdn}.

\vspace{0.5 cm}
The following fundamental theorem  was proven in \cite{GUO} and in its statement it is introduced formally the notion of Guo's index.

\begin{theorem}\cite [Theorem 2.1]{GUO}
\label{Guo} Let $(\lambda_{1},\ldots,\lambda_{n-1})$ be a closed under complex conjugation
$(n-1)$-tuple then, there exists a real number $\lambda_0$ (called Guo\ {'}s index) where
$$\max_{{1}\leq j\leq n-1}{|\lambda_j|}\leq\lambda_0.
$$
such that the list $(\lambda,\lambda_{1},\ldots,\lambda_{n-1})$ is realizable by an $n$-by-$n$ nonnegative matrix $A$ if and only if $\lambda\geq \lambda_0$. Furthermore, $\lambda_0\leq 2n\max_{1\leq j\leq n-1}{|\lambda_j|}$.

\end{theorem}

\noindent We define permutative matrix, below.

\begin{definition}
\cite{PP}
A square matrix of order $n$ with $n\geq 2$ is called a \textit{permutative matrix} or permutative when all its rows (up to the first one) are permutations of precisely its first row.
\end{definition}
The spectra of a class of permutative matrices was studied in \cite{MAR}.
In particular, spectral results for matrices partitioned into $2$-by-$2$ symmetric blocks were presented and, using these results sufficient conditions on a given list to be the list of eigenvalues of a nonnegative permutative matrix were obtained and the corresponding permutative matrices were constructed.

\noindent This paper is structured in $4$ sections. In the second section we obtain necessary and suficient conditions for a list $\Lambda$ to be the spectrum of a class of permutative matrices. In the third section results about circulant and block matrices, given in \cite{AMRH} are revisited.
In the fourth section necessary and sufficient conditions for some lists to be realized by a class of structured matrices are exhibited.

\section{Classes of Permutative Matrices}
\noindent In this section some auxiliary results from \cite{PP} are recalled and some new definitions are introduced.
In \cite{PP} the following results were proven.

\begin{lemma}
\label{pappa copy(1)}\ \cite[Lemma 3.1]{PP} For $\mathbf{x}=\left(
x_{1},x_{2},\ldots,x_{n}\right)  ^{T}\in\mathbb{C}^{n}$, let
\begin{equation}
X=
\begin{pmatrix}
x_{1} & x_{2} & \ldots & x_{i} & \ldots & x_{n-1} & x_{n}\\
x_{2} & x_{1} & \ldots & x_{i} & \ldots & x_{n-1} & x_{n}\\
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots\\
x_{i} & x_{2} & \ddots & x_{1} & \ddots & \vdots & \vdots\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
x_{n-1} & x_{2} & \ldots & \vdots & \vdots & x_{1} & x_{n}\\
x_{n} & x_{2} & \ldots & x_{i} & \ldots & x_{n-1} & x_{1}
\end{pmatrix}
.\label{mX}
\end{equation}
Then, the set of eigenvalues of $X$ is given by
\begin{equation}
\sigma(X)=\left\{

{\displaystyle\sum\limits_{i=1}^{n}}

x_{i},x_{1}-x_{2},x_{1}-x_{3},\ldots,x_{1}-x_{n}\right\}.
\end{equation}
\end{lemma}
\begin{definition}
{\rm The list $\Lambda=\left(\lambda_1,\ldots,\lambda_n\right)$ is a \textit{Sule\u{\i}manova spectrum} if the $
\Lambda$ is real list, $\lambda _{1}>0\geq \lambda _{2}\geq
\cdots \geq \lambda _{n}$ and $\sum_{i=1}^{n}\lambda_i \geq 0$.}
\end{definition}
\begin{theorem} \label{pappa} \cite{PP} Let $\Lambda=\left( \lambda_{1},\ldots,\lambda
_{n}\right)  $ be a Sule\u{\i}manova spectrum and consider the $n$-tuple
$\mathbf{x=}\left(  x_{1},x_{2},\ldots,x_{n}\right)  $, where
\[
\begin{tabular}
[c]{ccc}
$x_{1}=\frac{\lambda_{1}+\cdots+\lambda_{n}}{n}$ & and & $x_{i}=x_{1}
-\lambda_{i}, \, 2\leq i\leq n,$
\end{tabular}
\
\]
then the matrix in (\ref{mX}) realizes $\Lambda$.
\end{theorem}

\begin{lemma}
\cite{PP}
Let $\mathbf{e}$ and $J$ be the all ones column vector and the all ones square matrix, respectively.
\label{mM}
Let
$$M=\begin{pmatrix}
1&\mathbf{e}^{T}\\
\mathbf{e}&-I_{n-1}
\end{pmatrix}$$
then
$$M^{-1}=\frac{1}{n}\begin{pmatrix}
1&\mathbf{e}^{T}\\
\mathbf{e} &J-nI_{n-1}
\end{pmatrix}$$
\end{lemma}
The following fact is an immediate consequence of Lemmas \ref{pappa copy(1)} and \ref{mM}.
\begin{remark}
\label{arbitrary_list}
Let $\Lambda=\left(\lambda_{1},\ldots, \lambda_{n}\right)$ and consider $\mathbf{x^{T}}=M^{-1}\Lambda^{T}$ then $\Lambda$  is the list of eigenvalues of the matrix $X$ in (\ref{mX}), where $\mathbf{x}=\left(x_{1},\ldots.x_{n}\right).$
\end{remark}

\noindent The following notions will be used in the sequel.

\begin{definition}
{\rm
\label{ept}
Let $\mathbf{\tau }=\left( \tau _{1},\ldots ,\tau _{n}\right) $ be an $n$-tuple whose elements are permutations in the symmetric group\ $S_{n}$, with $\tau _{1}=id$.\ Let $\mathbf{a=}\left( a_{1},\ldots ,a_{n}\right) \in
\mathbb{C}^{n}$. Define the row-vector,
\begin{equation*}
\tau _{j}\left( \mathbf{a}\right) =\left( a_{\tau _{j}\left( 1\right)
},\ldots ,a_{\tau _{j}\left( n\right) }\right)
\end{equation*}
and consider the matrix
\begin{equation}
\tau \left( \mathbf{a}\right) =
\begin{pmatrix}
\tau _{1}\left( \mathbf{a}\right)   &
\tau _{2}\left( \mathbf{a}\right)  &
\ldots &
\tau _{n-1}\left( \mathbf{a}\right)  &
\tau _{n}\left( \mathbf{a}\right)
\end{pmatrix}^{T}
.  \label{permut}
\end{equation}

\noindent A square matrix $A$, is called $\mathbf{\tau}$\emph{-permutative} if
$A=\tau \left( \mathbf{a}\right) $ for some $n$-tuple $\mathbf{a}$.}
\end{definition}

\begin{definition}\cite{MAR}
{\rm
If $A$ and $B$ are $\mathbf{\tau }$-permutative by a common vector
$\mathbf{\tau }=\left( \tau _{1},\ldots ,\tau _{n}\right)$
then they are called \textit{permutatively equivalent}.}
\end{definition}

\noindent We now need to define the following concept.

\begin{definition}
If $A$ and $B$ are permutatively equivalent matrices then $B$ is \textit{$A$-like permutative} or $A$ is \textit{$B$-like permutative}.
\end{definition}

\begin{remark}

\label{important2} A permutative matrix $A$ defines the class of permutatively equivalent matrices: The class of the $A$-like permutative matrices. Let $\sigma_{1}$ be an arbitrary Sule\u{\i}manova
spectra, then the corresponding realizing matrix $X_{\sigma_{1}}$
given by Theorem \ref{pappa} is a $X$-like permutative matrix, where $X$ is as the matrix in (\ref{mX}). Furthermore,  by Lemma \ref{pappa copy(1)} and Remark \ref{arbitrary_list} it is easy to check that given an arbitrary $n$-tuple (not necessarily into the NIEP) there exist a solution which is $X$ -like permutative, where $X$ is as the matrix in (\ref{mX}). By simplicity, during the paper we use $X$-like permutative matrix to refer a $X$-like permutative matrix, where $X$ is as the matrix in (\ref{mX}).
\end{remark}
\noindent The following definition concerns to the spectra.

\begin{definition}
\label{XlikeperSpc}
Given the list $\Lambda =\left( \lambda_0 ,\lambda _{1},\lambda
_{2},\ldots ,\lambda _{n-1}\right) $ we say that $
\Lambda $ is \textit{ $X$-like permutative list} if there exists a nonnegative $X$-like permutative matrix whose spectrum is $\Lambda$.
\end{definition}

 By Theorem \ref{pappa} the Sule\u{\i}manova lists are $X$-like permutative. Also the list $\Lambda =\left( 24 ,5,6,7,8\right) $ is a $X$-like permutative list as the $X$-like permutative matrix whose first row is $(10,2,3,4,5)$ realizes $\Lambda$.

 \begin{remark}
 \label{real-spectrum}
 By the equations in Theorem \ref{pappa}, a $X$-like permutative spectrum is always a real spectrum.
 \end{remark}
\noindent The following result is a necessary and sufficient condition for the list $\Lambda=\left(\lambda_1,\lambda_2,\ldots,\lambda_n\right)$ to be a $X$-like permutative list.
\begin{theorem}
\label{necessary_suff}
Let $\Lambda=\left(\lambda_1,\lambda_2,\ldots,\lambda_n\right),$ be a real list, where $\lambda_1=\max _{ 2\leq \ell \leq n }{ \left| { \lambda  }_{ \ell  } \right|  } $, and $\sum _{ j=1  }^{ n }{ { \lambda  }_{ j }} \geq0.$ Then the set formed by the components of $\Lambda$ are the eigenvalues of a nonnegative irreducible $X$-like permutaitive matrix if and only if
\begin{eqnarray}
\label{ineq_perm}
{ \lambda  }_{ 1 }+(n-1){ \lambda  }_{ \nu (i) }\geq \sum _{ j=2,\  j\neq i  }^{ n }{ { \lambda  }_{ \nu (j) } },
\end{eqnarray}
for all $2\leq i\leq n$ and for some $\nu \in S_{n-1},$ the symmetric group of the permutations of the set $\{2,\ldots,n\}.$
In consequence, the expression $$\min _{ \nu \in { S }_{ n-1 } }{ \max _{ 2\leq i\leq n }{ \sum _{ j=2,\quad j\neq i }^{ n }{ { \lambda  }_{ \nu (j) } }  }  } -(n-1){ \lambda  }_{ \nu (i) }$$ is a Guo index for $X$-like permutative lists.
\end{theorem}

\begin{proof}
If there exits a permutation $\nu \in S_{n-1}$ such that the inequality in (\ref{ineq_perm}) holds then the vector
$\mathbf{x^{T}}=M^{-1}\mathbf{\Lambda^{T}_{\nu}},$
is nonnegative, where $$\mathbf{\Lambda_{\nu}}=\left(\lambda_1,\lambda_{\nu(2)},\ldots,\lambda_{\nu(n)}\right),$$ by the matrix equations in Remark \ref{arbitrary_list} we conclude that a nonnegative $X$-like permutative matrix whose first row is $\mathbf{x}$ has the components of $\Lambda$ as eigenvalues.
Reciprocally, if the components of $\Lambda$ are the eigenvalues of a nonnegative $X$-like permutative matrix whose first row is $\mathbf{x}$, by Remark \ref{arbitrary_list} $\mathbf{x}^{T}=M^{-1}\Lambda^{T}_{\mu} $ for some permutation $\mu$ in $S_{n-1}$, then by the non-negativity of $\mathbf{x}$ the inequalities in (\ref{ineq_perm}) hold for the  permutation $\mu$.
\end{proof}

\bigskip

\noindent By simplicity, during the paper, a $X $-like permutative matrix whose first row is $\mathbf{x}=\left(x_1,\ldots,x_n\right)$ is written
\begin{eqnarray*}
per_X\left(x_1,\ldots,x_n\right) \quad \text{or} \quad per_X\left(\mathbf{x}\right).
\end{eqnarray*}
\bigskip
\noindent For $\mathbf{\tau}$-permutative or $\cdot \ $-like permutative matrices an analogous property of circulant matrices was proven in \cite{MAR}.

\begin{proposition}
\label{cristi}
Let $\left\{ A_{i}\right\} _{i=1}^{k}$ be a family of pairwise permutatively equivalent square matrices.
Let $\left\{ \gamma _{i}\right\} _{i=1}^{k}$ be a set of complex numbers. Consider
\begin{equation}
A=\sum\limits_{i=1}^{k}\gamma _{i}A_{i}.
\end{equation}
Then $A$ is a $A_{1}$-like permutative matrix.
\end{proposition}

\section{Matrices partitioned into circulant blocks}

\noindent The class of circulant matrices and their properties are introduced in \cite{Karner}.
Let $\mathbf{a}=\left( a_{0},a_{1},\ldots ,a_{m-1}\right)$ be $m$-tuple of complex numbers.

\begin{definition} \cite{Karner}
A \emph{\ real circulant matrix} is a matrix of the form
\begin{equation*}
circ\left( \mathbf{a}\right) =
\begin{pmatrix}
a_{0} & a_{1} & \ldots  & \ldots & a_{m-1} \\
a_{m-1} & a_{0} & a_{1} & \ldots & a_{m-2} \\
a_{m-2} & \ddots  & \ddots  & \ddots  & \vdots  \\
\vdots  & \ddots  & \ddots  & a_{0} & a_{1} \\
a_{1} & \ldots  & a_{m-2} & a_{m-1} & a_{0}
\end{pmatrix}
\end{equation*}
\end{definition}

\bigskip

\noindent The next concepts can be seen in \cite{Karner}. The entries of the unitary discrete Fourier transform (DFT) matrix $F=\left(
f_{pq}\right) $ are given by
\begin{equation}
\label{fourier-m}
f_{pq}=\frac{1}{\sqrt{n}}\omega ^{pq},\quad 0\leq p, q\leq m-1\ ,
\end{equation}
where
\begin{equation}
\label{omega_root}
\omega =\cos \frac{2\pi }{m}+i\sin \frac{2\pi }{m}.
\end{equation}

\noindent The following results characterize the circulant spectra.

\begin{theorem}
\label{teorema 22}
\cite{Karner} Let $\mathbf{a}=(a_0,\ldots,a_{m-1})$ and $A(\mathbf{a})=circ(a_0,\ldots,a_{m-1}).$ Then $$A\left( \mathbf{a}\right) =FD \left( \mathbf{a}\right) F^{\ast },$$ with
$$
D\left( \mathbf{a}\right) =diag\left( \lambda _{0}\left( \mathbf{a}\right) ,\lambda
_{1}\left( \mathbf{a}\right) ,\ldots ,\lambda _{m-1}\left( \mathbf{a}\right) \right) $$
and
\begin{eqnarray}
\label{eigenvalues}
\text{\ }\lambda _{k}\left( \mathbf{a}\right) =\sum\limits_{\ell=0}^{m-1}a_{\ell}\omega
^{k\ell}\text{,\quad\ }0\leq k \leq m-1.
\end{eqnarray}
\end{theorem}

\begin{corollary}
\label{fund} Let $\mathbf{a}$ defined as in Theorem \ref{teorema 22} and consider $$\Lambda=\Lambda(\mathbf{a})=\left( \lambda _{0}\left( \mathbf{a}\right) ,\lambda _{1}\left(
\mathbf{a}\right) ,\ldots ,\lambda _{m-1}\left( \mathbf{a}\right) \right) .$$
Then,
\begin{eqnarray}
\label{coefficients}
a_{k}=\frac{1}{m}\sum\limits_{\ell=0}^{m-1}\lambda _{\ell}\omega ^{-k\ell}\text{
,\quad } 0 \leq k \leq m-1.
\end{eqnarray}
\end{corollary}

\noindent In \cite{AMRH}, using the techniques in \cite{MAR} for block matrices with circulant blocks, the following spectral result was proven.

\begin{theorem}
\cite{AMRH}
\label{main}
Let $K$ be an algebraically closed field of characteristic $0$ and suppose
that $A=\left( A(i,j)\right) $ is an $mn$-by-$mn$ matrix partitioned into $n^2$ circulant blocks of $m$-by-$m$ matrices, where for $ 1\leq i,j\leq n,$
\begin{equation}
\label{mtcsa}
A=\left( A(i,j)\right), \ A(i,j)=circ\left(\mathbf{a}(i,j)\right),
\end{equation}
where
\begin{eqnarray*}
\mathbf{a}(i,j)=(a_0(i,j),\ldots,a_{m-1}(i,j)),
\\
a_k(i,j)\in K,\ 1\leq i,j\leq n, \quad  0\leq k\leq m-1.
\end{eqnarray*}
Then
\begin{eqnarray}
\label{unionofsets}
\sigma \left( A\right) =\bigcup_{k=0}^{m-1}\sigma \left( S_k\right),
\end{eqnarray}
where
\begin{align}
\label{mtcsk}
S_k&=\left( s_k(i,j)\right)_{1\leq i,j\leq n}, \
s_k(i,j)=\sum\limits_{\ell=0}^{m-1}a_{\ell}\left(i,j\right)\omega
^{k\ell}.
\end{align}

\end{theorem}

\noindent The next result is a direct consequence of Theorem \ref{main} and of (\ref{mtcsk}).
\begin{corollary}
\cite{AMRH}
\label{choose}
Consider $\mathbf{a}(u,v)=(a_0(u,v),\ldots, a_{m-1}(u,v))$ and $A(u,v)=circ\left(\mathbf{a}(u,v)\right).$ For $1\leq \ell \leq m$, let matrix $S_{\ell}$, related to the circulant blocks $A(u,v)$ defined in (\ref{mtcsk}). For $ 0\leq k \leq m-1,$ let
\begin{eqnarray*}
L_k&=&\frac{1}{m}\sum\limits_{\ell=0}^{m-1} S _{\ell}\omega ^{-k\ell}, \qquad \text{then} \\
L_k
&=&\begin{pmatrix}
a_k(1,1) & a_k(1,2)&\ldots& a_k(1,m)\\
\vdots&\vdots&\ddots&\vdots\\
a_k(m,1) & a_k(m,2)&\ldots& a_k(m,m)
\end{pmatrix},
\end{eqnarray*}

In consequence, the matrix $A$ in (\ref{mtcsa}) is nonnegative if and only if for all $0\leq k \leq m-1$ the matrix $L_k$ is nonnegative and, in this case the matrix $S_{0}$ is nonnegative.
\end{corollary}

\noindent From Theorem \ref{main} the following inverse result was obtained.

\begin{corollary}
\cite{AMRH}
\label{converse2}
Let $\left( S_{\ell }^{'}\right) _{\ell =0}^{m-1}$ be $m$ $n$-by-$n$ complex matrices. Then there exists a matrix $A^{'}$ partitioned into blocks where each block is circulant and whose spectrum is given by
\begin{eqnarray}
\label{unionofsets2}
\sigma \left( A^{'}\right) =\bigcup_{\ell=0}^{m-1}\sigma \left( S_{\ell}^{'}\right),
\end{eqnarray}
\end{corollary}

\noindent The following notions will be used in the sequel.

\begin{definition}
\cite{AMRH}
A matrix partitioned into blocks is called \textit{block permutative matrix} when all its row blocks (up to the first one) are permutations of precisely its first row block.
\end{definition}

\noindent The class of  the block $X$-like permutative  matrices is defined as follows.

\begin{definition}
Let $X=\left(x_{uv}\right)$ be the square matrix in (\ref{mX}). A block permutative matrix with circulant blocks $A=\left(circ(\mathbf{a}(u.v)\right)$ is a block $X$-like permutative matrix providing that, for all  $1\leq u,v\leq n$,
the block $circ\left(\mathbf{a}(u,v)\right)$ is the $(u,v)$-th block in $A$ if and only if $x_{uv}$ is the $(u,v)$-th entry in $X$.
\end{definition}
\begin{theorem}
\cite{AMRH}
Let $A$ be the matrix partitioned into blocks as defined in (\ref{mtcsa}). For $0\leq k \leq m-1$ let $S_k$ be the class of matrices related to $A$ defined in (\ref{mtcsk}). The matrix $A$ is a block permutative matrix with circulant blocks if and only if the matrices $S_k$ are pairwise permutatively equivalent.
\end{theorem}

\section{An inverse problem related to block permutative matrices with circulant blocks}

\noindent In this section we study the Guo index to block permutative matrices with circulant blocks, which are a subclass of permutative matrices. Let $\mathbf{q}_1,\mathbf{q}_2,\ldots,\mathbf{q}_m$ denotes the canonical vectors

\noindent To our purpose we establish the following result.
\begin{theorem}
\label{strongguo}
Let $E=(\varepsilon_{ij})$ be an $n$-by-$m$ matr\noindent ix where the multiset $\left\{ E\right\} $ formed by the entries of $E$ is closed under complex conjugation, the set of the entries in the first column of $E$ is a $X$-like permutative list and the sum of all row sums of $E$ is nonnegative. Suppose that $\varepsilon_{11}$ is positive and has the largest absolute value among the absolute values of entries of $E$.  Moreover, for $1\leq \ell \leq \left \lfloor \tfrac{m}{2} \right \rfloor,$
\begin{eqnarray}
\label{conjugatecondition3}
E\mathbf{q}_{\ell+1}=\overline{E\mathbf{q}_{m-\ell+1}}
\end{eqnarray}
that is, the entries of the $(m-\ell+1)$-th column of $E$ are the corresponding complex conjugate entries of the $(\ell+1)$-th column of $E.$ Note that for $m=2h$ the condition in (\ref{conjugatecondition3}) implies that the column $Eq_{h+1}$ of $E$ has real entries.
If
\begin{eqnarray}
\label{new1}
\varepsilon_{11}\geq \Phi
\end{eqnarray}
with
\[
\Phi =\max_{\substack{ 0\leq k\leq m-1 \\ 0\leq j\leq n-1}}-\left[
\sum_{p=1}^{n-1}\varepsilon _{(p+1)1}+\sum_{\ell
=1}^{m-1}\sum_{p=0}^{n-1}\varepsilon _{(p+1)(\ell +1)}\omega ^{-k\ell
}-n\sum_{\ell =1}^{m-1}\varepsilon _{(p+1)(\ell +1)}\omega ^{-k\ell }\right]
\]
Then $\left \{ E \right \}$ is the spectrum of a nonnegative $X$-like block permutative matrix $A$ whose blocks are circulant.
\end{theorem}

\begin{proof}

By the conditions of the statement there exists a nonnegative permutative  \[S_0:=per_X\left(
s_{00},s_{10},\ldots ,s_{(n-1)0}\right) \] whose spectrum is $\left \{ Eq_{1} \right \}$ (the set of the entries in $Eq_1$).
The condition in (\ref{conjugatecondition3}) implies that for $1\leq \ell\leq \left \lfloor \frac{m}{2} \right \rfloor$ the

$X$-like permutative matrices $S_{\ell}$ and $S_{m-\ell}$ whose spectrum are $\left \{ E\mathbf{q}_{(\ell+1)} \right \}$ and $\left \{ E\mathbf{q}_{(m-\ell+1)} \right \}$, respectively, are related by
$\overline{S}_{\ell}=S_{m-\ell}$. For $ 1 \leq \ell \leq m-1$,
suppose that
\begin{equation*}
S_{\ell}=per_X\left( s\left( \ell\right) \right) \text{, with }s\left( \ell\right)
=\left( s_{0\ell},s_{1\ell},\ldots ,s_{(n-1)\ell}\right) ,
\end{equation*}
where
\begin{equation}
s\left( \ell\right)^{T} =M^{-1} E\mathbf{q}_{\ell+1} \label{circsl},
\end{equation}
then

\begin{eqnarray}
\label{s-entries}
s_{0\ell}&=&\frac{1}{n}\left[\sum_{p=1}^{n}\varepsilon_{p(\ell+1)}\right] \quad and\\
s_{j\ell}&=&\frac{1}{n}\left[\sum_{p=1}^{n}\varepsilon_{p(\ell+1)}-n\varepsilon_{(j+1)(\ell+1)}\right], \quad 1\leq j\leq n-1.
\end{eqnarray}
For $0\leq k \leq m-1$, the entries of the $n$-by-$n$ $X$-like permutative matrix can be obtained, using equation (\ref{coefficients}) and the entries of the sums
\begin{equation}
L_k=\frac{1}{m}S_0+\frac{1}{m}\sum_{\ell =1}^{m-1}S_{\ell }\omega ^{-k\ell
}, \label{circlkp1}
\end{equation}

By Proposition \ref{cristi} the linear combination of $X$-like permutative matrices are  $X$-like permutative then matrices $L_k$ in (\ref{circlkp1})  are $X$-like permutative. Suppose that $$L_k=per_X\left(a_0(k),\ldots, a_{n-1}(k)\right).$$
From (\ref{circlkp1}), for $ 0\leq j \leq n-1,$ the following
holds

\begin{eqnarray*}
a_j(k) &=&\frac{1}{m}\left( s_{j0}+\sum_{\ell =1}^{m-1}\omega ^{-k\ell
}s_{j\ell } \right).
\end{eqnarray*}
Using (\ref{s-entries}), for $1\leq j \leq n-1$ we must have
\small{
\begin{eqnarray*}
0 \leq a_j(k)&=&\frac{1}{m}\left( s_{j0}+\sum_{\ell =1}^{m-1}\omega ^{-k\ell
}s_{j\ell } \right)\\
             & = &\small{\frac{1}{m}}\frac{1}{n}\left(
               \left[\varepsilon_{11}+\sum\limits_{p=1}^{n-1}\varepsilon_{(p+1)1}\right]+\sum_{\ell =1}^{m-1}\omega ^{-k\ell}\left[\sum\limits_{p=0}^{n-1}\varepsilon_{(p+1)(\ell+1)}-n\varepsilon_{(j+1)(\ell+1)}\right]

               \right) \\
             &= &\small{\frac{1}{mn}}\left(\varepsilon_{11}+\sum\limits_{p=1}^{n-1}\varepsilon_{(p+1)1}+\sum_{\ell =1}^{m-1}\sum\limits_{p=0}^{n-1}\varepsilon_{(p+1)(\ell+1)}\omega ^{-k\ell}-n\sum_{\ell =1}^{m-1}\omega ^{-k\ell}\varepsilon_{(j+1)(\ell+1)}\right)
\end{eqnarray*}}
\noindent for all $0\leq k\leq  m-1.$ Therefore, the last condition implies the inequality in (\ref{new1}).
\end{proof}

\begin{remark}
To computational aims it is worth note that the columns of the product $$L=\frac{1}{\sqrt{m}}M^{-1}EF^{*}$$ are the first rows of the matrices $L_0,\ldots L_{m-1}.$
\end{remark}

\noindent Now, one can formulate the following question.
\begin{problem}
Which condition (or conditions) is (or are) necessary and sufficient for the existence of a nonnegative matrix, $A$ $X$-like block permutative matrix with circulant blocks whose spectrum equals to $\left \{ E \right \}$,? where $E=\left( \varepsilon _{ij}\right)$ is as in Theorem \ref{strongguo},
\end{problem}

 \noindent Let us consider the set
\[
\boldsymbol{P}=\left\{ f:\left\{ E\right\} \rightarrow \left\{ E\right\} :f
\text{ }is\ bijective\right\}
\]
\begin{definition}
The function $f\in \boldsymbol{P}$ is said to be \textit{$E$-nonnegative spectrally stable ($E$-NNSS)} if
the matrix $E\left( f\right) =\left( f\left( \varepsilon _{ij}\right)
\right) $ is such that
$f\left( \varepsilon _{11}\right) $ has the maximum absolute value among $
f\left( \varepsilon _{ij}\right), $ the first column of $E\left( f\right) $ is real and it is a $X$-like permutative list, the
$\left( m-\ell +1 \right) $-th column of $E\left( f\right) $ is the complex
conjugate column of the $\left( \ell +1\right) $-th column  of  $E\left(
f\right) $, and then
\[
E\left( f\right) \mathbf{q}_{(m-\ell +1) }=\overline{E\left( f\right) }\mathbf{q}_{\left( \ell
+1\right) },
\]
for $1 \leq \ell \leq \left \lfloor \frac{m}{2}  \right \rfloor.$
\end{definition}

For instance:

\begin{enumerate}

\item The identity function of $E$ into $E$ is clearly $E$-NNSS.
\item   $f:\left\{ E\right\} \rightarrow \left\{ E\right\} $ defined by
\[
f\left( \varepsilon _{ij}\right) =\left \{
\begin{array}{ll}
\varepsilon _{ij} & j\neq 2 \quad {\small \text{and}} \quad j\neq m, \\
\varepsilon_{i m } & j=2, \\
\varepsilon _{i2} & j=m;
\end{array}
\right.
\]
is $E$-NNSS.
\item  $f:\left\{ E\right\} \rightarrow \left\{ E\right\} $ defined by
\[
f\left( \varepsilon _{ij}\right) =\overline{\varepsilon }_{ij}\mbox{\, for all\,} i,j
\]
is $E$-NNSS.
\item  $f:\left\{ E\right\} \rightarrow \left\{ E\right\} $ defined by
\[
f\left( \varepsilon_{ij}\right) =
\left\{
\begin{array}{ll}
\varepsilon_{ij} & \mbox{\, if \,} j=1,\\
\overline{\varepsilon}_{ij} & \mbox{\,if \,} j\neq 1;
\end{array}
\right.
\]
is $E$-NNSS.
\end{enumerate}
We denote by $\boldsymbol{P}^{*}$ the subset of $\boldsymbol{P}$ formed by all $E$-NNSS bijections of $E$.
Note that if $f \in P^{*}$ then $f(\varepsilon_{11})=\varepsilon_{11}.$

\begin{theorem}

Let $E=(\varepsilon_{ij})$ be an $n$-by-$m$ matrix such that its first row is a $X$-like permutative spectrum. Moreover, the multiset $\left\{E\right\}$ formed by the entries of $E$ satisfies the conditions in Theorem \ref{strongguo}.
The multiset $\left \{ E \right \}$ is the spectrum of a block $X$-like permutative matrix $A$ whose blocks are circulant if and only if

\begin{eqnarray}
\label{maria}
\varepsilon_{11} &\geq &
\min_{f\in \boldsymbol{P}^{*}}
\max\left\{\Theta: 0\leq k \leq m-1, \ 0\leq j \leq n-1\right\}
\end{eqnarray}
where,
\begin{eqnarray*}
\Theta &  = &
 -\left[\sum\limits_{p=1}^{n-1}f(\varepsilon_{(p+1)1})+\sum_{\ell =1}^{m-1}\sum\limits_{p=0}^{n-1}f(\varepsilon_{(p+1)(\ell+1)})\omega ^{-k\ell}-n\sum_{\ell =1}^{m-1}\omega ^{-k\ell}f(\varepsilon_{(j+1)(\ell+1)}) \right].
\end{eqnarray*}

\end{theorem}

\begin{proof}
Following the same steps of the above proof this time replacing $\varepsilon_{ij}$ by $f(\varepsilon_{ij})$ we arrive at the inequality in (\ref{new1}). After taking the minimum when the function $f$ vary into $\boldsymbol{P}^{*}$, the inequality (\ref{maria}) is obtained.
\end{proof}

\begin{example}
    Let consider
    \[
    E=
    \begin{pmatrix}
    23.9 & i & -i \\
    -3 & 1-7i & 1+7i\\
    0 & -3+i & -3-i
    \end{pmatrix}
    \]
   \noindent  The nonnegative $X$-like permutative matrix $per_X(6.9667, 9.9667,6.9667) $ has the set formed by the components of $E\mathbf{q}_1$ as spectrum. In addition we have
    \begin{eqnarray*}
    L_{0} &=&per_X\left(1.8778, 2.2111, 3.8778\right)\\
    L_{1} &=&per_X\left(1.5822, 6.9570, 0,0048\right)\\
    L_{2} &=&per_X\left(3.5067, 0.7986, 3.0840\right).\\
    \end{eqnarray*}

   \noindent In consequence, the circulant blocks are

    \begin{eqnarray*}
    A_{0} &=&circ\left(1.8778, 1.5822, 3.5067\right)\\
    A_{1} &=&circ\left(2.2111, 6.9570, 0.7986\right)\\
    A_{2} &=&circ\left(3.8778, 0,0048, 3.0840\right)\\
    \end{eqnarray*}

  \noindent  Therefore, the $X$-like block permutative matrix
    \[\begin{pmatrix}
    A_0 & A_1 & A_2\\
    A_1 & A_0 & A_2\\
    A_2 & A_1 & A_0
    \end{pmatrix}\]

 \noindent has spectrum the multiset $\left\{E\right\}.$
    \end{example}

    \begin{example}
    Let consider
    \[
    E_{1}=
    \begin{pmatrix}
    5 & -3 & -2 & -3\\
    2 & 1 & 2 & 1
    \end{pmatrix}
    \]
    \noindent  The nonnegative $X$-like permutative matrix $per_X(3.5,1.5) $ has the set formed by the components of $E\mathbf{q}_1$ as spectrum. In addition we have
   \noindent the matrices
    \begin{eqnarray*}
    L_{0} =per_{X}\left(1.5,0\right), \ L_{1} =per_{X}\left(2,2\right), \ L_{2}= per_{X}\left(2.5, 2\right), \ L_{3}= per_{X}\left(2, 2\right).
    \end{eqnarray*}

   \noindent   In consequence, we obtain
    \begin{eqnarray*}
    A_{0} =circ\left(1.5,2, 2.5, 2\right), \ A_{1} =circ\left(0,2,2,2\right).
    \end{eqnarray*}

 \noindent   Therefore, the $X$-like block permutative matrix
    \[\begin{pmatrix}

    A_0 & A_1 \\
    A_1 & A_0
    \end{pmatrix}\]

\noindent    has spectrum the multiset $\left\{E_1\right\}.$

\end{example}

\begin{example}
\noindent    Let consider
    \[
    E_{2}=
    \begin{pmatrix}
    2.5 & 0.25i & 0 & -0.25i \\
    -1 & 0.5-i & 0 & 0.5+i
    \end{pmatrix}
    \]
  \noindent  thus, it is obtained
    \begin{eqnarray*}
    L_{0}=per_X\left(0.25, 0.375\right),\ L_{1}= per_X\left(0, 0.75\right),\\& \\  L_{2}= per_X\left(0.125, 0.5\right)\ L_{3}= per_X\left(0.375, 0.125\right).
    \end{eqnarray*}
\noindent    In consequence,
    \begin{eqnarray*}
    A_{0} = circ\left(0.25,0.0, 0.125,0.375 \right),\
    A_{1} = circ\left(0.375, 0.75, 0.5, 0.125\right).
    \end{eqnarray*}

\noindent    Therefore, the $X$-like block permutative matrix
    \[\begin{pmatrix}
    A_0 & A_1 \\
    A_1 & A_0
    \end{pmatrix}\]

  \noindent  has spectrum the multiset $\left\{E_{2}\right\}.$

\noindent By consider in $E_2(1,1)=2.49$ in a place of $E_2(1,1)=2.5$ it is obtained
\begin{eqnarray*}
    L_{0} &=&per_X\left(0.2488,0.3738\right)\\
    L_{1} &=&per_X\left(-0.0012, 0.7488\right)\\
    L_{2}&=& per_X\left(0.1238, 0.4987\right)\\
    L_{3}&=& per_X\left(0.3738, 0.1238\right).
    \end{eqnarray*}
    \noindent    Therefore, the $X$-like block permutative matrix that we can construct is no nonnegative.
\end{example}

\begin{example}
\noindent    Let consider
    \[
    E_{3}=
    \begin{pmatrix}
    4 & 1 & 1 \\
    -1 & -2.5 & -2.5
    \end{pmatrix}
    \]
  \noindent Thus are obtained the matrices
    \begin{eqnarray*}
    L_{0} =per_X\left(0,2\right),\   L_{1} =per_X\left(0.75,0.25\right),\
    L_{2}= per_X\left(0.75, 0.25\right).
    \end{eqnarray*}
\noindent    In consequence,
    \begin{eqnarray*}
    A_{0} =circ\left(0,0.75, 0.75\right),\    A_{1} =circ\left(2,0.25,0.25\right).
    \end{eqnarray*}

\noindent    Therefore, the $X$-like block permutative matrix
    \[\begin{pmatrix}
    A_0 & A_1 \\
    A_1 & A_0
    \end{pmatrix}\]

  \noindent  has spectrum the multiset $\left\{E_{3}\right\}.$
    Considering the multiset formed by the entries of $E_{1}, 4$ is the least Perron root that can be considered because the trace becomes negative if the spectral radius is diminished.
\end{example}

\textbf{References}.


TITLE: Probability of selection without replacement and dependent removal
QUESTION [1 upvotes]: Suppose my friend has a bag with 3 green marbles and 2 red marbles. I take out a single marble at random and put it aside. If the marble I take out is green, then my friend takes out a single red marble at random and puts it aside. I then take out another single marble at random from the remaining marbles in the bag. What is the probability that I take out 2 green marbles?
Suppose I label the marbles in the bag: g1, g2, g3, r1, r2. I then have the following possible outcomes:
g1 is taken out, then r1 is taken out, then g2 is taken out
g1 is taken out, then r1 is taken out, then g3 is taken out
g1 is taken out, then r1 is taken out, then r2 is taken out

g2 is taken out, then r1 is taken out, then g1 is taken out
g2 is taken out, then r1 is taken out, then g3 is taken out
g2 is taken out, then r1 is taken out, then r2 is taken out

g3 is taken out, then r1 is taken out, then g1 is taken out
g3 is taken out, then r1 is taken out, then g2 is taken out
g3 is taken out, then r1 is taken out, then r2 is taken out

g1 is taken out, then r2 is taken out, then g2 is taken out
g1 is taken out, then r2 is taken out, then g3 is taken out
g1 is taken out, then r2 is taken out, then r1 is taken out

g2 is taken out, then r2 is taken out, then g1 is taken out
g2 is taken out, then r2 is taken out, then g3 is taken out
g2 is taken out, then r2 is taken out, then r1 is taken out

g3 is taken out, then r2 is taken out, then g1 is taken out
g3 is taken out, then r2 is taken out, then g2 is taken out
g3 is taken out, then r2 is taken out, then r1 is taken out

r1 is taken out, then g1 is taken out
r1 is taken out, then g2 is taken out
r1 is taken out, then g3 is taken out
r1 is taken out, then r2 is taken out

r2 is taken out, then g1 is taken out
r2 is taken out, then g2 is taken out
r2 is taken out, then g3 is taken out
r2 is taken out, then r1 is taken out

I count 26 possible outcomes. 12 of these result in 2 green marbles being taken out. I would therefore conclude that the probability of taking out 2 green marbles is 12/26 or 6/13.
However, I have read the following statement:

Two events that happen sequentially are not always independent. The
  occurrence of one event may affect the occurrence of a following
  event. In that case, the probability that both events happen is equal
  to the probability that the first event happens multiplied by the
  probability that given that the first event has already happened, the
  second event happens as well.

I would say that the probability of first taking out a green marble is 3/5. Given that I have taken out a green marble, the probability that I take out another green marble is 2/3. I would therefore conclude from this statement that the probability of taking out 2 green marbles is (3/5)*(2/3) = 6/15.
These two approaches give different results. What have I missed?

REPLY [1 votes]: The second method and answer are correct.
The $26$ possibilities in your list are not equally likely. So we cannot simply count and divide.
For example, $(g_1, r_1, g_2)$ has probability $(1/5)(1/2)(1/3)$ while $(r_2,g_1)$ has probability $(1/5)(1/4)$.


TITLE: Are there quantum states between the conduction band and the valence band?
QUESTION [0 upvotes]: Neamen's book states that the Fermi-Dirac distribution can be interpreted as the ratio of filled to total quantum states at any energy. For intrinsic materials, the value of Fermi-Dirac distribution at the Fermi level, which is in the middle of the conduction band and valence band, is 0.5. Does that mean quantum states and electrons exist in the forbidden energy gap? This seems to contradict with the definition of the forbidden energy gap. Please help! Thanks.

REPLY [2 votes]: You need two ingredients to have electrons in some state

Non void density of states (DOS)
Non zero probability

If any of those ingredients fail, you'll have no electrons there.
In the case you mention, Fermi-Dirac's probability indicates that there is some probability of having electrons in the gap. However, the density of state says that there are no states there. So no matter how high the probability is, if there are no allowed states there, you'll have no electrons.
In the same way, if the DOS says that you have a band there, but the probability is zero, then that band is empty. If the probability changes then it can be filled.
In sum, you need both things, and they are independent.


TITLE: Seating arrangement of $5$ men and $5$ women stand in a row so that no $2$ men and no $2$ women are adjacent to each other?
QUESTION [0 upvotes]: How many ways in which $5$ men and $5$ women stand in a row so that no $2$ men and no $2$ women are adjacent to each other?

REPLY [0 votes]: Let's think about this and sequence the problem into discrete tasks starting at seat one and moving to seat ten.
For your first seat you have $10$ individuals to choose from. For your second seat you cannot choose the same type of individual you chose for your first seat so you have $5$ ways to choose an individual for your second seat, for your third seat you have $4$ ways to choose an individual since you already chose one of this type of individual for your first seat... and so on.
We arrive at:
$$10 \cdot 5 \cdot 4 \cdot 4 \cdot 3 \cdot 3 \cdot 2 \cdot 2 \cdot 1 \cdot 1$$
or alternatively
$$10 \cdot 5! \cdot 4!.$$
To expand on the OP's comment. When we are concerned with arrangements of $4$ girls and $5$ boys such that no two girls are together, we can enumerate the possibilities by choosing $4$ slots out of the six slots that exist between our boys and then count all permutations of our boys and girls. Thus the answer is ${6 \choose 4} \cdot 5! \cdot 4!$.
However, in the question posed here, this argument does not work since if we try to do $6 \choose 5$ and place our girls between our five boys we will count arrangements where boys are next to one another since we don't have enough girls to guarantee that every slot between two boys is filled. Thus we need to fix an ordering and it is clear that we can either seat a girl first, or a boy first. We can look at either selecting an arbitrary person for the first seat (such as my model above) or we can look at cases and combine the results (such as the other answer did).
If one really desired a model involving combinations, you could model as follows. Let us seat our girls in this order where an $x$ denotes an empty seat: $xGxGxGxGxG$, now since we have exactly five seats and exactly five boys we can seat our boys in $5 \choose 5$ ways. Then for this arrangement we have ${5 \choose 5} \cdot 5! \cdot 5!$ valid arrangements. Now let us seat our girls as $GxGxGxGxGx$. Again we are in the clear here since we have $10$ seats total and enough boys to ensure there is one between every pair of girls. Then for this arrangement we have ${5 \choose 5} \cdot 5! \cdot 5!$. Combining our two possibilities we arrive at
$$ {5 \choose 5} \cdot 5! \cdot 5! +{5 \choose 5} \cdot 5! \cdot 5!= 2\cdot5!\cdot5!. $$


TITLE: Domaine of an adjoint operator
QUESTION [1 upvotes]: Let $A$ be the derivative operator which defined on $L^2(0,1)$ with domain $$D(A) = \left\{ {v \in {H^1}(0,1),v(0) = 0} \right\}.$$
It is obvious that with an integration by part we find that $A^*=A$ with
$$D(A^*) = \left\{ {v \in {H^1}(0,1),v(1) = 0} \right\}.$$
My question is: For $A^*$ to be the adjoint of $A$, they should have the same domaine, but herre I don't see that. Can we say that $A^*=A$?
Thank you.

REPLY [1 votes]: For an unbounded operator, the domain of the operator and the domain of the adjoint do not necessarily agree. You have the correct domain for $A^*$ in the statement of your problem. $A\ne A^*$. That is, this is not a selfadjoint operator. The only selfadjoint version of $i\frac{d}{dt}$ has a domain with periodic conditions of the form $v(2\pi)=e^{i\theta}v(0)$ for some $\theta$. You can check that this leads to a symmetric operator:
\begin{align}
  \langle if',g\rangle-\langle f,ig'\rangle & =  \int_{0}^{2\pi}if'(t)\overline{g(t)}-f(t)\overline{ig'(t)}dt \\
   & = i\int_{0}^{2\pi}f(t)\overline{g'(t)}+f'(t)\overline{g(t)}dt \\
   & = if\overline{g}|_{0}^{2\pi} \\ & = if(2\pi)\overline{g(2\pi)}-if(0)\overline{g(0)} \\
   & = if(0)\overline{g(0)}-if(0)\overline{g(0)}=0.
\end{align}
And this is selfadjoint on $H^1(0,1)$ with the given endpoint condition. These are the only selfadjoint versions of $i\frac{d}{dt}$ on $H^1(0,1)$.
Your $A$ is not selfadjoint, and that happens because the domain of $A^*$ is not the same. But you have correctly identified $\mathcal{D}(A^*)$ for your $A$.


TITLE: The norm $\|S-Q\|_F$ where $Q$ is orthogonal is minimised by $Q=I$
QUESTION [2 upvotes]: Problem:
Suppose that $S$ is symmetric and semi-positive-definite. Let $\|\cdot \|_F$ be the Frobenius norm. Show that
$$\|S-I \|_F \leq \|S-Q\|_F$$
for all orthogonal matrices $Q$, where $I$ is the identity matrix.

Attempt:
So from what I know, the Frobenius norm is defined as
$$\|A\|_F:= \bigg(\sum_{i,j} a_{ij}^2\bigg)^{1/2}$$
and one of the properties of it is that $\|A\|_F = \big(\sum_i \sigma_i^2 \big)^{1/2}$ where $\sigma_i$ are the Singular Values of $A$.
Also, $\|QA\|_F = \|AQ\|_F = \|A\|_F$ for any orthogonal matrix $Q$.
Thus, if we consider the Singular Value Decomposition of $S$, say $S=UDV$ where $U,V$ are orthogonal and $D = \text{diag}(\sigma_1,\dots,\sigma_n)$, then
$$\|S-I\|_F = \|UDV - I\|_F = \|D - U^TV^T\|_F$$
but I feel like I'm not getting anyhere with this approach.
$\color{red}{\text{In particular,}}$ I don't really know how to use the fact that $S$ is symmetric and semi-positive-definite. Does this have any effect on the form of the SVD for $S$?
Any help would be much appreciated. Thanks!

REPLY [1 votes]: The fact that $S$ is symmetric and positive semi-definite means it has a spectral decomposition $S = U D U^T$ where $D$ is a diagonal matrix whose entries are all non-negative, and $U$ is orthogonal. So we are looking for the minimum of
$$\|U D U^T - UU^T Q\|_F = \|D U^T - U^TQ\|_F = \|D U^T - U^T Q U U^{T}\|_F = \|D - U^T Q U\|_F$$
But note that since $Q$ is any orthogonal matrix, and $U$ is also orthogonal, $U^T Q U$ can also take on any orthogonal matrix. So the problem reduces to minimizing $\|D - Q\|$, for $Q$ orthogonal. Note that since $\|A\|_F = \text{tr}(A^T A)$ for real matrices $A$, it follows that $$\|D - Q\|_F = \text{tr}((D - Q)^T (D- Q)) = \text{tr}(D^2) - \text{tr}(Q^T D + D Q) + \text{tr}(I)$$
The second equality follows because trace is linear. But note that $DQ$ and $Q^T D$ are transposes of each other, so we just must find $Q$ that maximizes $\text{tr}(Q^T D)$. But it's clear that $\text{tr}(Q^T D)$ is maximized when all entries of $Q$ are along the diagonal, and as large as possible. In particular, since the diagonal entries of an orthogonal matrix are always less than or equal to $1$, it follows that
$$\text{tr}(Q^T D) \leq \text{tr}(D)$$
Note that this equality is satisfied when $Q^T = Q = I$, so indeed $\text{tr}(Q^T D)$ is maximized when $Q = I$. Therefore, the orthogonal matrix $Q$ that minimizes
$\|S - Q\|_F$ is equal to $U^T I U = I$. $\square$


TITLE: Proper Zariski closed sets of the Parabola
QUESTION [2 upvotes]: Can any one help me to understand why all the proper Zariski closed sets of the parabola
$V=\mathbb{V}(y-x^2)\subseteq\mathbb{A}^2$ are finite?Indeed, the Zariski topology on any plane curve is the co-finite topology, provided the curve is not a union of two other curves.

REPLY [1 votes]: The key of understanding what you said is that for a curve $f(x,y)=0$ in $\Bbb A(K)^2$ the closed Zariski subsets correspond (roughly) to ideals $I\subseteq A:=K[x,y]/(f(x,y))$. The geometrical points in the closed set corresponding to the ideal $I$ are given by the maximal ideals containing $I$ (to avoid headaches one may assume that $K$ is algebraically closed, e.g. $K=\Bbb C$).
One knows that:

There is a 1-1 correspondence between ideals in $A$ and ideals in $K[x,y]$ containing $f(x,y)$
If the curve (equivalently: the polynomial $f(x,y)$) is irreducible, every non-zero prime ideal in $A$ is maximal.

Thus, either $I$ in $A$ is the zero ideal and the whole curve is the closed set corresponding to it, or $I$ is not zero and so is contained in only finitely many maximal ideals.
When the curve is not irreducible, say $f(x,y)=g_1(x,y)g_2(x,y)$ as product of irreducibles, then the ideals $I_1=(g_1)$ and $I_2=(g_2)$ are prime in $A$ but not maximal and correspond to infinite Zariski closed sets contained in the curve (namely, the two components).


TITLE: Explicit formula for higher order derivatives in higher dimensions
QUESTION [4 upvotes]: Let $f:\mathbb{R}^n\to\mathbb{R}^m$ be a function at least $C^k$ and fix some point $x_0\in\mathbb{R}^n$. I want an explicit formula for its derivatives of higher order.
I already read this threads:
What are higher derivatives?
Using higher order derivatives
One thing is clear, $D^kf(x_0)$ is a $k$-linear map from $\underbrace{\mathbb{R}^n\times\ldots\times\mathbb{R}^n}_{k \text{ times}}$ to $\mathbb{R}^m$. Yet, the answers given do not address my question, they only give the abstract description but I want a concrete description.
For $k=1$ we have that $Df(x_0)v = [Df(x_0)]\cdot v$, where $ [Df(x_0)] = \left(\frac{\partial f_i(x_0)}{\partial x_j}\right)$ stands for the Jacobian matrix of $Df(x_0)$. So we have an explicit formula.
For $k\geq 2$, it's not clear how to get an explicit formula for $D^kf(x_0)(v_1,\ldots,v_k)$ from the definition and the case $k=1$. There must be some way to do this.
I hope you can help me. Thank you very much.

REPLY [4 votes]: Write $${\bf v}_1 =\sum_{i_1=1}^n v_1^{i_1}{\bf e}_{i_1}, \cdots , {\bf v}_k =\sum_{i_k=1}^n v_k^{i_k}{\bf e}_{i_k},$$where $\{{\bf e}_1,\ldots, {\bf e}_n\}$ is the standard basis. Also, let $\{{\bf e}^\ast_1,\ldots, {\bf e}^\ast_n\}$ be the dual basis. Then:
$$\begin{align} D^kf({\bf x}_0)({\bf v}_1,\cdots,{\bf v}_k) &= D^kf({\bf x}_0)\left(\sum_{i_1=1}^n v_1^{i_1}{\bf e}_{i_1},\cdots,  \sum_{i_k=1}^n v_k^{i_k}{\bf e}_{i_k}\right)  \\ &= \sum_{i_1,\ldots,i_k=1}^n v_1^{i_1}\ldots v_k^{i_k} D^kf({\bf x}_0)({\bf e}_{i_1},\cdots,{\bf e}_{i_k}) \\ &=\sum_{i_1,\ldots,i_k=1}^n v_1^{i_1}\ldots v_k^{i_k} \frac{\partial^k f}{\partial x_{i_1}\cdots \partial x_{i_k}}({\bf x}_0) \\ &= \sum_{i_1,\ldots,i_k=1}^n \frac{\partial^k f}{\partial x_{i_1}\cdots \partial x_{i_k}}({\bf x}_0) {\bf e}^\ast_{i_1}\otimes \cdots \otimes {\bf e}^\ast_{i_k}({\bf v}_1,\cdots,{\bf v}_k) \end{align}$$Hence: $$D^kf({\bf x}_0) = \sum_{i_1,\cdots,i_k=1}^n \frac{\partial^k f}{\partial x_{i_1}\cdots \partial x_{i_k}}({\bf x}_0) {\bf e}^\ast_{i_1}\otimes \cdots \otimes {\bf e}^\ast_{i_k}. $$
We could have used any basis instead of the standard one - the only difference is that we'd have iterated directional derivatives as the coefficients of that tensor in the new basis. I guess that's as concrete we can get.


text:
/-
Copyright (c) 2017 Johannes Hölzl. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Johannes Hölzl, Mario Carneiro
-/
import measure_theory.measure.outer_measure
import order.filter.countable_Inter
import data.set.accumulate

/-!
# Measure spaces

This file defines measure spaces, the almost-everywhere filter and ae_measurable functions.
See `measure_theory.measure_space` for their properties and for extended documentation.

Given a measurable space `α`, a measure on `α` is a function that sends measurable sets to the
extended nonnegative reals that satisfies the following conditions:
1. `μ ∅ = 0`;
2. `μ` is countably additive. This means that the measure of a countable union of pairwise disjoint
   sets is equal to the measure of the individual sets.

Every measure can be canonically extended to an outer measure, so that it assigns values to
all subsets, not just the measurable subsets. On the other hand, a measure that is countably
additive on measurable sets can be restricted to measurable sets to obtain a measure.
In this file a measure is defined to be an outer measure that is countably additive on
measurable sets, with the additional assumption that the outer measure is the canonical
extension of the restricted measure.

Measures on `α` form a complete lattice, and are closed under scalar multiplication with `ℝ≥0∞`.

## Implementation notes

Given `μ : measure α`, `μ s` is the value of the *outer measure* applied to `s`.
This conveniently allows us to apply the measure to sets without proving that they are measurable.
We get countable subadditivity for all sets, but only countable additivity for measurable sets.

See the documentation of `measure_theory.measure_space` for ways to construct measures and proving
that two measure are equal.

A `measure_space` is a class that is a measurable space with a canonical measure.
The measure is denoted `volume`.

This file does not import `measure_theory.measurable_space`, but only `measurable_space_def`.

## References

* <https://en.wikipedia.org/wiki/Measure_(mathematics)>
* <https://en.wikipedia.org/wiki/Almost_everywhere>

## Tags

measure, almost everywhere, measure space
-/

noncomputable theory

open classical set filter (hiding map) function measurable_space
open_locale classical topological_space big_operators filter ennreal nnreal

variables {α β γ δ ι : Type*}

namespace measure_theory

/-- A measure is defined to be an outer measure that is countably additive on
measurable sets, with the additional assumption that the outer measure is the canonical
extension of the restricted measure. -/
structure measure (α : Type*) [measurable_space α] extends outer_measure α :=
(m_Union ⦃f : ℕ → set α⦄ :
  (∀ i, measurable_set (f i)) → pairwise (disjoint on f) →
  measure_of (⋃ i, f i) = ∑' i, measure_of (f i))
(trimmed : to_outer_measure.trim = to_outer_measure)

/-- Measure projections for a measure space.

For measurable sets this returns the measure assigned by the `measure_of` field in `measure`.
But we can extend this to _all_ sets, but using the outer measure. This gives us monotonicity and
subadditivity for all sets.
-/
instance measure.has_coe_to_fun [measurable_space α] :
  has_coe_to_fun (measure α) (λ _, set α → ℝ≥0∞) :=
⟨λ m, m.to_outer_measure⟩

section

variables [measurable_space α] {μ μ₁ μ₂ : measure α} {s s₁ s₂ t : set α}

namespace measure

/-! ### General facts about measures -/

/-- Obtain a measure by giving a countably additive function that sends `∅` to `0`. -/
def of_measurable (m : Π (s : set α), measurable_set s → ℝ≥0∞)
  (m0 : m ∅ measurable_set.empty = 0)
  (mU : ∀ {{f : ℕ → set α}} (h : ∀ i, measurable_set (f i)), pairwise (disjoint on f) →
    m (⋃ i, f i) (measurable_set.Union h) = ∑' i, m (f i) (h i)) : measure α :=
{ m_Union := λ f hf hd,
  show induced_outer_measure m _ m0 (Union f) =
      ∑' i, induced_outer_measure m _ m0 (f i), begin
    rw [induced_outer_measure_eq m0 mU, mU hf hd],
    congr, funext n, rw induced_outer_measure_eq m0 mU
  end,
  trimmed :=
  show (induced_outer_measure m _ m0).trim = induced_outer_measure m _ m0, begin
    unfold outer_measure.trim,
    congr, funext s hs,
    exact induced_outer_measure_eq m0 mU hs
  end,
  ..induced_outer_measure m _ m0 }

lemma of_measurable_apply {m : Π (s : set α), measurable_set s → ℝ≥0∞}
  {m0 : m ∅ measurable_set.empty = 0}
  {mU : ∀ {{f : ℕ → set α}} (h : ∀ i, measurable_set (f i)), pairwise (disjoint on f) →
    m (⋃ i, f i) (measurable_set.Union h) = ∑' i, m (f i) (h i)}
  (s : set α) (hs : measurable_set s) : of_measurable m m0 mU s = m s hs :=
induced_outer_measure_eq m0 mU hs

lemma to_outer_measure_injective : injective (to_outer_measure : measure α → outer_measure α) :=
λ ⟨m₁, u₁, h₁⟩ ⟨m₂, u₂, h₂⟩ h, by { congr, exact h }

@[ext] lemma ext (h : ∀ s, measurable_set s → μ₁ s = μ₂ s) : μ₁ = μ₂ :=
to_outer_measure_injective $ by rw [← trimmed, outer_measure.trim_congr h, trimmed]

lemma ext_iff : μ₁ = μ₂ ↔ ∀ s, measurable_set s → μ₁ s = μ₂ s :=
⟨by { rintro rfl s hs, refl }, measure.ext⟩

end measure

@[simp] lemma coe_to_outer_measure : ⇑μ.to_outer_measure = μ := rfl

lemma to_outer_measure_apply (s : set α) : μ.to_outer_measure s = μ s := rfl

lemma measure_eq_trim (s : set α) : μ s = μ.to_outer_measure.trim s :=
by rw μ.trimmed; refl

lemma measure_eq_infi (s : set α) : μ s = ⨅ t (st : s ⊆ t) (ht : measurable_set t), μ t :=
by rw [measure_eq_trim, outer_measure.trim_eq_infi]; refl

/-- A variant of `measure_eq_infi` which has a single `infi`. This is useful when applying a
  lemma next that only works for non-empty infima, in which case you can use
  `nonempty_measurable_superset`. -/
lemma measure_eq_infi' (μ : measure α) (s : set α) :
  μ s = ⨅ t : { t // s ⊆ t ∧ measurable_set t}, μ t :=
by simp_rw [infi_subtype, infi_and, subtype.coe_mk, ← measure_eq_infi]

lemma measure_eq_induced_outer_measure :
  μ s = induced_outer_measure (λ s _, μ s) measurable_set.empty μ.empty s :=
measure_eq_trim _

lemma to_outer_measure_eq_induced_outer_measure :
  μ.to_outer_measure = induced_outer_measure (λ s _, μ s) measurable_set.empty μ.empty :=
μ.trimmed.symm

lemma measure_eq_extend (hs : measurable_set s) :
  μ s = extend (λ t (ht : measurable_set t), μ t) s :=
(extend_eq _ hs).symm

@[simp] lemma measure_empty : μ ∅ = 0 := μ.empty

lemma nonempty_of_measure_ne_zero (h : μ s ≠ 0) : s.nonempty :=
ne_empty_iff_nonempty.1 $ λ h', h $ h'.symm ▸ measure_empty

lemma measure_mono (h : s₁ ⊆ s₂) : μ s₁ ≤ μ s₂ := μ.mono h

lemma measure_mono_null (h : s₁ ⊆ s₂) (h₂ : μ s₂ = 0) : μ s₁ = 0 :=
nonpos_iff_eq_zero.1 $ h₂ ▸ measure_mono h

lemma measure_mono_top (h : s₁ ⊆ s₂) (h₁ : μ s₁ = ∞) : μ s₂ = ∞ :=
top_unique $ h₁ ▸ measure_mono h

/-- For every set there exists a measurable superset of the same measure. -/
lemma exists_measurable_superset (μ : measure α) (s : set α) :
  ∃ t, s ⊆ t ∧ measurable_set t ∧ μ t = μ s :=
by simpa only [← measure_eq_trim] using μ.to_outer_measure.exists_measurable_superset_eq_trim s

/-- For every set `s` and a countable collection of measures `μ i` there exists a measurable
superset `t ⊇ s` such that each measure `μ i` takes the same value on `s` and `t`. -/
lemma exists_measurable_superset_forall_eq {ι} [encodable ι] (μ : ι → measure α) (s : set α) :
  ∃ t, s ⊆ t ∧ measurable_set t ∧ ∀ i, μ i t = μ i s :=
by simpa only [← measure_eq_trim]
  using outer_measure.exists_measurable_superset_forall_eq_trim (λ i, (μ i).to_outer_measure) s

lemma exists_measurable_superset₂ (μ ν : measure α) (s : set α) :
  ∃ t, s ⊆ t ∧ measurable_set t ∧ μ t = μ s ∧ ν t = ν s :=
by simpa only [bool.forall_bool.trans and.comm]
  using exists_measurable_superset_forall_eq (λ b, cond b μ ν) s

lemma exists_measurable_superset_of_null (h : μ s = 0) :
  ∃ t, s ⊆ t ∧ measurable_set t ∧ μ t = 0 :=
h ▸ exists_measurable_superset μ s

lemma exists_measurable_superset_iff_measure_eq_zero :
  (∃ t, s ⊆ t ∧ measurable_set t ∧ μ t = 0) ↔ μ s = 0 :=
⟨λ ⟨t, hst, _, ht⟩, measure_mono_null hst ht, exists_measurable_superset_of_null⟩

theorem measure_Union_le [encodable β] (s : β → set α) : μ (⋃ i, s i) ≤ ∑' i, μ (s i) :=
μ.to_outer_measure.Union _

lemma measure_bUnion_le {s : set β} (hs : s.countable) (f : β → set α) :
  μ (⋃ b ∈ s, f b) ≤ ∑' p : s, μ (f p) :=
begin
  haveI := hs.to_encodable,
  rw [bUnion_eq_Union],
  apply measure_Union_le
end

lemma measure_bUnion_finset_le (s : finset β) (f : β → set α) :
  μ (⋃ b ∈ s, f b) ≤ ∑ p in s, μ (f p) :=
begin
  rw [← finset.sum_attach, finset.attach_eq_univ, ← tsum_fintype],
  exact measure_bUnion_le s.countable_to_set f
end

lemma measure_Union_fintype_le [fintype β] (f : β → set α) :
  μ (⋃ b, f b) ≤ ∑ p, μ (f p) :=
by { convert measure_bUnion_finset_le finset.univ f, simp }

lemma measure_bUnion_lt_top {s : set β} {f : β → set α} (hs : s.finite)
  (hfin : ∀ i ∈ s, μ (f i) ≠ ∞) : μ (⋃ i ∈ s, f i) < ∞ :=
begin
  convert (measure_bUnion_finset_le hs.to_finset f).trans_lt _,
  { ext, rw [finite.mem_to_finset] },
  apply ennreal.sum_lt_top, simpa only [finite.mem_to_finset]
end

lemma measure_Union_null [encodable β] {s : β → set α} :
  (∀ i, μ (s i) = 0) → μ (⋃ i, s i) = 0 :=
μ.to_outer_measure.Union_null

@[simp] lemma measure_Union_null_iff [encodable ι] {s : ι → set α} :
  μ (⋃ i, s i) = 0 ↔ ∀ i, μ (s i) = 0 :=
μ.to_outer_measure.Union_null_iff

lemma measure_bUnion_null_iff {s : set ι} (hs : s.countable) {t : ι → set α} :
  μ (⋃ i ∈ s, t i) = 0 ↔ ∀ i ∈ s, μ (t i) = 0 :=
μ.to_outer_measure.bUnion_null_iff hs

lemma measure_sUnion_null_iff {S : set (set α)} (hS : S.countable) :
  μ (⋃₀ S) = 0 ↔ ∀ s ∈ S, μ s = 0 :=
μ.to_outer_measure.sUnion_null_iff hS

theorem measure_union_le (s₁ s₂ : set α) : μ (s₁ ∪ s₂) ≤ μ s₁ + μ s₂ :=
μ.to_outer_measure.union _ _

lemma measure_union_null : μ s₁ = 0 → μ s₂ = 0 → μ (s₁ ∪ s₂) = 0 :=
μ.to_outer_measure.union_null

@[simp] lemma measure_union_null_iff : μ (s₁ ∪ s₂) = 0 ↔ μ s₁ = 0 ∧ μ s₂ = 0:=
⟨λ h, ⟨measure_mono_null (subset_union_left _ _) h, measure_mono_null (subset_union_right _ _) h⟩,
  λ h, measure_union_null h.1 h.2⟩

lemma measure_union_lt_top (hs : μ s < ∞) (ht : μ t < ∞) : μ (s ∪ t) < ∞ :=
(measure_union_le s t).trans_lt (ennreal.add_lt_top.mpr ⟨hs, ht⟩)

@[simp] lemma measure_union_lt_top_iff : μ (s ∪ t) < ∞ ↔ μ s < ∞ ∧ μ t < ∞ :=
begin
  refine ⟨λ h, ⟨_, _⟩, λ h, measure_union_lt_top h.1 h.2⟩,
  { exact (measure_mono (set.subset_union_left s t)).trans_lt h, },
  { exact (measure_mono (set.subset_union_right s t)).trans_lt h, },
end

lemma measure_union_ne_top (hs : μ s ≠ ∞) (ht : μ t ≠ ∞) : μ (s ∪ t) ≠ ∞ :=
(measure_union_lt_top hs.lt_top ht.lt_top).ne

@[simp] lemma measure_union_eq_top_iff : μ (s ∪ t) = ∞ ↔ μ s = ∞ ∨ μ t = ∞ :=
not_iff_not.1 $ by simp only [← lt_top_iff_ne_top, ← ne.def, not_or_distrib,
  measure_union_lt_top_iff]

lemma exists_measure_pos_of_not_measure_Union_null [encodable β] {s : β → set α}
  (hs : μ (⋃ n, s n) ≠ 0) : ∃ n, 0 < μ (s n) :=
begin
  contrapose! hs,
  exact measure_Union_null (λ n, nonpos_iff_eq_zero.1 (hs n))
end

lemma measure_inter_lt_top_of_left_ne_top (hs_finite : μ s ≠ ∞) : μ (s ∩ t) < ∞ :=
(measure_mono (set.inter_subset_left s t)).trans_lt hs_finite.lt_top

lemma measure_inter_lt_top_of_right_ne_top (ht_finite : μ t ≠ ∞) : μ (s ∩ t) < ∞ :=
inter_comm t s ▸ measure_inter_lt_top_of_left_ne_top ht_finite

lemma measure_inter_null_of_null_right (S : set α) {T : set α} (h : μ T = 0) : μ (S ∩ T) = 0 :=
measure_mono_null (inter_subset_right S T) h

lemma measure_inter_null_of_null_left {S : set α} (T : set α) (h : μ S = 0) : μ (S ∩ T) = 0 :=
measure_mono_null (inter_subset_left S T) h

/-! ### The almost everywhere filter -/

/-- The “almost everywhere” filter of co-null sets. -/
def measure.ae {α} {m : measurable_space α} (μ : measure α) : filter α :=
{ sets := {s | μ sᶜ = 0},
  univ_sets := by simp,
  inter_sets := λ s t hs ht, by simp only [compl_inter, mem_set_of_eq];
    exact measure_union_null hs ht,
  sets_of_superset := λ s t hs hst, measure_mono_null (set.compl_subset_compl.2 hst) hs }

notation `∀ᵐ` binders ` ∂` μ `, ` r:(scoped P, filter.eventually P (measure.ae μ)) := r
notation `∃ᵐ` binders ` ∂` μ `, ` r:(scoped P, filter.frequently P (measure.ae μ)) := r
notation f ` =ᵐ[`:50 μ:50 `] `:0 g:50 := f =ᶠ[measure.ae μ] g
notation f ` ≤ᵐ[`:50 μ:50 `] `:0 g:50 := f ≤ᶠ[measure.ae μ] g

lemma mem_ae_iff {s : set α} : s ∈ μ.ae ↔ μ sᶜ = 0 := iff.rfl

lemma ae_iff {p : α → Prop} : (∀ᵐ a ∂ μ, p a) ↔ μ { a | ¬ p a } = 0 := iff.rfl

lemma compl_mem_ae_iff {s : set α} : sᶜ ∈ μ.ae ↔ μ s = 0 := by simp only [mem_ae_iff, compl_compl]

lemma frequently_ae_iff {p : α → Prop} : (∃ᵐ a ∂μ, p a) ↔ μ {a | p a} ≠ 0 :=
not_congr compl_mem_ae_iff

lemma frequently_ae_mem_iff {s : set α} : (∃ᵐ a ∂μ, a ∈ s) ↔ μ s ≠ 0 :=
not_congr compl_mem_ae_iff

lemma measure_zero_iff_ae_nmem {s : set α} : μ s = 0 ↔ ∀ᵐ a ∂ μ, a ∉ s :=
compl_mem_ae_iff.symm

lemma ae_of_all {p : α → Prop} (μ : measure α) : (∀ a, p a) → ∀ᵐ a ∂ μ, p a :=
eventually_of_forall

--instance ae_is_measurably_generated : is_measurably_generated μ.ae :=
--⟨λ s hs, let ⟨t, hst, htm, htμ⟩ := exists_measurable_superset_of_null hs in
--  ⟨tᶜ, compl_mem_ae_iff.2 htμ, htm.compl, compl_subset_comm.1 hst⟩⟩

instance : countable_Inter_filter μ.ae :=
⟨begin
  intros S hSc hS,
  rw [mem_ae_iff, compl_sInter, sUnion_image],
  exact (measure_bUnion_null_iff hSc).2 hS
end⟩

lemma ae_imp_iff {p : α → Prop} {q : Prop} : (∀ᵐ x ∂μ, q → p x) ↔ (q → ∀ᵐ x ∂μ, p x) :=
filter.eventually_imp_distrib_left

lemma ae_all_iff [encodable ι] {p : α → ι → Prop} :
  (∀ᵐ a ∂ μ, ∀ i, p a i) ↔ (∀ i, ∀ᵐ a ∂ μ, p a i) :=
eventually_countable_forall

lemma ae_ball_iff {S : set ι} (hS : S.countable) {p : Π (x : α) (i ∈ S), Prop} :
  (∀ᵐ x ∂ μ, ∀ i ∈ S, p x i ‹_›) ↔ ∀ i ∈ S, ∀ᵐ x ∂ μ, p x i ‹_› :=
eventually_countable_ball hS

lemma ae_eq_refl (f : α → δ) : f =ᵐ[μ] f := eventually_eq.rfl

lemma ae_eq_symm {f g : α → δ} (h : f =ᵐ[μ] g) : g =ᵐ[μ] f :=
h.symm

lemma ae_eq_trans {f g h: α → δ} (h₁ : f =ᵐ[μ] g) (h₂ : g =ᵐ[μ] h) :
  f =ᵐ[μ] h :=
h₁.trans h₂

lemma ae_le_of_ae_lt {f g : α → ℝ≥0∞} (h : ∀ᵐ x ∂μ, f x < g x) : f ≤ᵐ[μ] g :=
begin
  rw [filter.eventually_le, ae_iff],
  rw ae_iff at h,
  refine measure_mono_null (λ x hx, _) h,
  exact not_lt.2 (le_of_lt (not_le.1 hx)),
end

@[simp] lemma ae_eq_empty : s =ᵐ[μ] (∅ : set α) ↔ μ s = 0 :=
eventually_eq_empty.trans $ by simp only [ae_iff, not_not, set_of_mem_eq]

@[simp] lemma ae_eq_univ : s =ᵐ[μ] (univ : set α) ↔ μ sᶜ = 0 := eventually_eq_univ

lemma ae_le_set : s ≤ᵐ[μ] t ↔ μ (s \ t) = 0 :=
calc s ≤ᵐ[μ] t ↔ ∀ᵐ x ∂μ, x ∈ s → x ∈ t : iff.rfl
           ... ↔ μ (s \ t) = 0          : by simp [ae_iff]; refl

lemma ae_le_set_inter {s' t' : set α} (h : s ≤ᵐ[μ] t) (h' : s' ≤ᵐ[μ] t') :
  (s ∩ s' : set α) ≤ᵐ[μ] (t ∩ t' : set α) :=
h.inter h'

@[simp] lemma union_ae_eq_right : (s ∪ t : set α) =ᵐ[μ] t ↔ μ (s \ t) = 0 :=
by simp [eventually_le_antisymm_iff, ae_le_set, union_diff_right,
  diff_eq_empty.2 (set.subset_union_right _ _)]

lemma diff_ae_eq_self : (s \ t : set α) =ᵐ[μ] s ↔ μ (s ∩ t) = 0 :=
by simp [eventually_le_antisymm_iff, ae_le_set, diff_diff_right,
  diff_diff, diff_eq_empty.2 (set.subset_union_right _ _)]

lemma diff_null_ae_eq_self (ht : μ t = 0) : (s \ t : set α) =ᵐ[μ] s :=
diff_ae_eq_self.mpr (measure_mono_null (inter_subset_right _ _) ht)

lemma ae_eq_set {s t : set α} :
  s =ᵐ[μ] t ↔ μ (s \ t) = 0 ∧ μ (t \ s) = 0 :=
by simp [eventually_le_antisymm_iff, ae_le_set]

lemma ae_eq_set_inter {s' t' : set α} (h : s =ᵐ[μ] t) (h' : s' =ᵐ[μ] t') :
  (s ∩ s' : set α) =ᵐ[μ] (t ∩ t' : set α) :=
h.inter h'

@[to_additive]
lemma _root_.set.mul_indicator_ae_eq_one {M : Type*} [has_one M] {f : α → M} {s : set α}
  (h : s.mul_indicator f =ᵐ[μ] 1) : μ (s ∩ function.mul_support f) = 0 :=
by simpa [filter.eventually_eq, ae_iff] using h

/-- If `s ⊆ t` modulo a set of measure `0`, then `μ s ≤ μ t`. -/
@[mono] lemma measure_mono_ae (H : s ≤ᵐ[μ] t) : μ s ≤ μ t :=
calc μ s ≤ μ (s ∪ t)       : measure_mono $ subset_union_left s t
     ... = μ (t ∪ s \ t)   : by rw [union_diff_self, set.union_comm]
     ... ≤ μ t + μ (s \ t) : measure_union_le _ _
     ... = μ t             : by rw [ae_le_set.1 H, add_zero]

alias measure_mono_ae ← _root_.filter.eventually_le.measure_le

/-- If two sets are equal modulo a set of measure zero, then `μ s = μ t`. -/
lemma measure_congr (H : s =ᵐ[μ] t) : μ s = μ t :=
le_antisymm H.le.measure_le H.symm.le.measure_le

alias measure_congr ← _root_.filter.eventually_eq.measure_eq

lemma measure_mono_null_ae (H : s ≤ᵐ[μ] t) (ht : μ t = 0) : μ s = 0 :=
nonpos_iff_eq_zero.1 $ ht ▸ H.measure_le

/-- A measurable set `t ⊇ s` such that `μ t = μ s`. It even satisfies `μ (t ∩ u) = μ (s ∩ u)` for
any measurable set `u` if `μ s ≠ ∞`, see `measure_to_measurable_inter`.
(This property holds without the assumption `μ s ≠ ∞` when the space is sigma-finite,
see `measure_to_measurable_inter_of_sigma_finite`).
If `s` is a null measurable set, then
we also have `t =ᵐ[μ] s`, see `null_measurable_set.to_measurable_ae_eq`.
This notion is sometimes called a "measurable hull" in the literature. -/
@[irreducible] def to_measurable (μ : measure α) (s : set α) : set α :=
if h : ∃ t ⊇ s, measurable_set t ∧ t =ᵐ[μ] s then h.some
else if h' : ∃ t ⊇ s, measurable_set t ∧ (∀ u, measurable_set u → μ (t ∩ u) = μ (s ∩ u))
  then h'.some
else (exists_measurable_superset μ s).some

lemma subset_to_measurable (μ : measure α) (s : set α) : s ⊆ to_measurable μ s :=
begin
  rw to_measurable, split_ifs with hs h's,
  exacts [hs.some_spec.fst, h's.some_spec.fst, (exists_measurable_superset μ s).some_spec.1]
end

lemma ae_le_to_measurable : s ≤ᵐ[μ] to_measurable μ s := (subset_to_measurable _ _).eventually_le

@[simp] lemma measurable_set_to_measurable (μ : measure α) (s : set α) :
  measurable_set (to_measurable μ s) :=
begin
  rw to_measurable, split_ifs with hs h's,
  exacts [hs.some_spec.snd.1, h's.some_spec.snd.1, (exists_measurable_superset μ s).some_spec.2.1]
end

@[simp] lemma measure_to_measurable (s : set α) : μ (to_measurable μ s) = μ s :=
begin
  rw to_measurable, split_ifs with hs h's,
  { exact measure_congr hs.some_spec.snd.2 },
  { simpa only [inter_univ] using h's.some_spec.snd.2 univ measurable_set.univ },
  { exact (exists_measurable_superset μ s).some_spec.2.2 }
end

/-- A measure space is a measurable space equipped with a
  measure, referred to as `volume`. -/
class measure_space (α : Type*) extends measurable_space α :=
(volume : measure α)

export measure_space (volume)

/-- `volume` is the canonical  measure on `α`. -/
add_decl_doc volume

section measure_space

notation `∀ᵐ` binders `, ` r:(scoped P, filter.eventually P
  (measure_theory.measure.ae measure_theory.measure_space.volume)) := r

notation `∃ᵐ` binders `, ` r:(scoped P, filter.frequently P
  (measure_theory.measure.ae measure_theory.measure_space.volume)) := r

/-- The tactic `exact volume`, to be used in optional (`auto_param`) arguments. -/
meta def volume_tac : tactic unit := `[exact measure_theory.measure_space.volume]

end measure_space

end

end measure_theory

section
open measure_theory

/-!
# Almost everywhere measurable functions

A function is almost everywhere measurable if it coincides almost everywhere with a measurable
function. We define this property, called `ae_measurable f μ`. It's properties are discussed in
`measure_theory.measure_space`.
-/

variables {m : measurable_space α} [measurable_space β]
  {f g : α → β} {μ ν : measure α}

/-- A function is almost everywhere measurable if it coincides almost everywhere with a measurable
function. -/
def ae_measurable {m : measurable_space α} (f : α → β) (μ : measure α . measure_theory.volume_tac) :
  Prop :=
∃ g : α → β, measurable g ∧ f =ᵐ[μ] g

lemma measurable.ae_measurable (h : measurable f) : ae_measurable f μ :=
⟨f, h, ae_eq_refl f⟩

namespace ae_measurable

/-- Given an almost everywhere measurable function `f`, associate to it a measurable function
that coincides with it almost everywhere. `f` is explicit in the definition to make sure that
it shows in pretty-printing. -/
def mk (f : α → β) (h : ae_measurable f μ) : α → β := classical.some h

lemma measurable_mk (h : ae_measurable f μ) : measurable (h.mk f) :=
(classical.some_spec h).1

lemma ae_eq_mk (h : ae_measurable f μ) : f =ᵐ[μ] (h.mk f) :=
(classical.some_spec h).2

lemma congr (hf : ae_measurable f μ) (h : f =ᵐ[μ] g) : ae_measurable g μ :=
⟨hf.mk f, hf.measurable_mk, h.symm.trans hf.ae_eq_mk⟩

end ae_measurable

lemma ae_measurable_congr (h : f =ᵐ[μ] g) :
  ae_measurable f μ ↔ ae_measurable g μ :=
⟨λ hf, ae_measurable.congr hf h, λ hg, ae_measurable.congr hg h.symm⟩

@[simp] lemma ae_measurable_const {b : β} : ae_measurable (λ a : α, b) μ :=
measurable_const.ae_measurable

lemma ae_measurable_id : ae_measurable id μ := measurable_id.ae_measurable

lemma ae_measurable_id' : ae_measurable (λ x, x) μ := measurable_id.ae_measurable

lemma measurable.comp_ae_measurable [measurable_space δ] {f : α → δ} {g : δ → β}
  (hg : measurable g) (hf : ae_measurable f μ) : ae_measurable (g ∘ f) μ :=
⟨g ∘ hf.mk f, hg.comp hf.measurable_mk, eventually_eq.fun_comp hf.ae_eq_mk _⟩

end

subset_name: curated