TITLE: Is the result of adding several positive semidefinite matrices also positive semidefinite?
QUESTION [2 upvotes]: I have a certain number of   nxn   matrices that are positive semidefinite. Is the result of adding all these matrices also positive semidefinite? If affirmative, is it always the case or, instead, in just some instances?
I would also appreciate if you can provide me with the proof or give me a reference I can consult.
Thanks in advance for your help.

REPLY [3 votes]: $\rm\bf Observation$: $\hskip 1.5in x^*(A+B)\,x=x^*A\,x+x^*B\,x$
$\rm\bf Rhetorical\;\;Question$: Now what happens if both $x^*A\,x\ge0$ and $x^*B\,x\ge0$?


text:
\begin{document}

\author{Mustapha Ait Rami$^1$,
Didier Henrion$^{2,3}$}

\footnotetext[1]{
Departamento de Ingenier\'{\i}a de Sistemas y Autom\'atica,
Facultad de Ciencias, Universidad de Valladolid, calle Real de Burgos s/n,
SP-47011 Valladolid, Spain. {\tt aitrami@autom.uva.es}}

\footnotetext[2]{
CNRS; LAAS; 7 avenue du colonel Roche, F-31077 Toulouse, France;
Universit\'e de Toulouse; UPS, INSA, INP, ISAE; LAAS; F-31077 Toulouse, France.
{\tt henrion@laas.fr}}

\footnotetext[3]{
Faculty of Electrical Engineering, Czech Technical University in Prague, Technick\'a 4,
CZ-16626 Prague, Czech Republic.
{\tt henrion@fel.cvut.cz}}

\maketitle

\begin{abstract}
Exploiting spectral properties of symmetric banded Toeplitz matrices, we describe simple sufficient conditions for positivity of a trigonometric polynomial formulated as linear matrix inequalities (LMI) in the coefficients. As an application of these results, we derive a hierarchy of convex LMI inner approximations (affine sections of the cone of positive definite matrices of size $m$) of the nonconvex set of Schur stable polynomials of given degree $n < m$. It is shown that when $m$ tends to infinity the hierarchy converges to a lifted LMI approximation (projection of an LMI set defined in a lifted space of dimension quadratic in $n$) already studied in the technical literature.
\end{abstract}

\begin{center}
\small
{\bf Keywords}: stability; positive polynomials; LMI; Toeplitz matrices
\end{center}

\section{Introduction}

Linear system stability can be formulated algebraically in the space
of coefficients of the characteristic polynomial. The region of stability
is generally {\it nonconvex} in this space, and this is a major
obstacle when solving fixed-order or robust controller design problems.
In the case of discrete-time linear systems, the region of stability
is a bounded open set whose boundary consists of (flat) hyperplanes and
nonconvex (negatively curved) algebraic varieties. Recent results on real algebraic
geometry and generalized problems of moments
can be used to build up a hierarchy of convex linear matrix inequality (LMI)
outer approximations of the region of stability, with asymptotic
convergence to its convex hull, see e.g. \cite{csm} for a software
implementation and examples. It is generally more difficult to
construct convex LMI {\it inner approximations}, see \cite{hsk03}
for a survey. Strict positive realness of rational transfer functions
and its connection with polynomial positivity conditions are
used in \cite{hsk03} to generate inner approximations which are
{\it lifted} LMI sets. For polynomials of degree $n$, they are projections
onto coefficient space $\mathbb{R}^n$ of an LMI set living in a
lifted space $\mathbb{R}^{\frac{n^2+3n}{2}}$. The LMI set is built
around a particular point, the central polynomial, whose relevance
in robust control design is explained in \cite{hsk03}. These lifted
LMI regions are also used in signal processing, see e.g.
\cite[Section 7.3]{dumitrescu}. They can be derived in a state-space
setting with the Kalman-Yakubovich-Popov lemma \cite{karimi}.

Whereas lifted LMIs are a powerful modeling paradigm (it is currently
conjectured that every convex semialgebraic set is a lifted LMI set),
the introduction of a large number of lifting variables can be seen
as a drawback. It is therefore relevant to build convex LMI inner
approximations of the nonconvex stability region {\it without
liftings}, namely as affine sections of the cone of positive
semidefinite matrices. This is the objective of this paper.
We use results of functional analysis on sequences of eigenvalues
of Toeplitz matrices to derive sufficient LMI conditions for positivity of
trigonometric polynomials, and we apply these results to construct
a hierarchy of $m$-by-$m$ LMI inner approximations of the nonconvex
stability domain. Moreover we prove that when $m$ tends to infinity,
the hierarchy converges asymptotically to the lifted
LMI approximation of \cite{hsk03}.

\section{Trigonometric polynomials and Toeplitz matrices}

Let $p_k$, $k=0,1,2,\ldots,n$ denote real numbers, and
define the trigonometric polynomial
\[
\begin{array}{r@{\;}c@{\;}l}
z=e^{i\theta} \mapsto p(\theta) & = & p_0+p_1(z+z^{-1})+p_2(z^2+z^{-2})+
\cdots+p_n(z^n+z^{-n}) \\
& = & p_0 + 2p_1\cos\theta + 2p_2\cos2\theta+\cdots+2p_n\cos n\theta
\end{array}
\]
of degree $n$ mapping the unit disk of the complex plane onto the real axis.

For a given integer $m > n$, define the column vector
$v_m(z) = [1 \ z \ z^2 \cdots z^{m-1}]^T$ and represent polynomial $p$
as a quadratic form
\begin{equation}\label{quad}
p(\theta) = \frac{1}{m}v^T_m(e^{-i\theta})P_mv_m(e^{i\theta})
\end{equation}
where
\begin{equation}\label{pm}
P_m = \left[\begin{array}{ccccc}
p_0 & \frac{m}{m-1}p_1 & \frac{m}{m-2}p_2 \\
\frac{m}{m-1}p_1 &  p_0  & \frac{m}{m-1}p_1\\
\frac{m}{m-2}p_2  & \frac{m}{m-1}p_1 & p_0\\
& & & \ddots \\
& & & & p_0
\end{array}\right]
\end{equation}
is an $m$-by-$m$ symmetric banded Toeplitz matrix.

Define
\[
R_m = \left[\begin{array}{ccccc}
p_0 & p_1 & p_2 \\
p_1 & p_0 & p_1 \\
p_2 & p_1 & p_0 \\
& & & \ddots \\
& & & & p_0
\end{array}\right]
\]
as the $m$-by-$m$ moment matrix of $p$, so named for
\[
p_k = \frac{1}{2\pi} \int_0^{2\pi} p(\theta)e^{-ik\theta} d\theta
\]
is the $k$-th moment, or Fourier coefficient, of polynomial $p$.
Note that $R_m$ has the
same banded symmetric Toeplitz structure as $P_m$.

Connections between the spectrum of matrix $R_m$ and
the values taken by polynomial $p$ on the unit circle
have been studied extensively.
In the sequel, $\lambda_{\min}$ denotes the minimum eigenvalue
of a symmetric matrix.

\begin{theorem}\label{Szego}
$$\lim_{m\rightarrow +\infty}\lambda_{\min}(R_m)=\min_\theta p(\theta).$$
\end{theorem}

\begin{proof}
It is a corollary of G\'abor Szeg\H{o}'s fundamental eigenvalue
distribution theorem, see e.g. \cite[Corollary 4.2]{gray}.
\end{proof}

In this section we aim at establishing a similar spectral property linking
matrix $P_m$ and polynomial $p$. First let us state a few instrumental
results.

\begin{lemma}\label{lem1}
For all $\theta$ it holds $\lambda_{\min}(P_m)\leq p(\theta)$ and as a consequence
\begin{equation}
\limsup_{m\rightarrow +\infty}\lambda_{\min}(P_m)\leq \min_\theta p(\theta).
\end{equation}
\end{lemma}

\begin{proof}
From relation (\ref{quad}) and the identity $v^T_m(e^{-i\theta})v_m(e^{i\theta})=m$,
it follows that
\begin{equation}\label{rayleigh}
\frac{v^T_m(e^{-i\theta})P_mv_m(e^{i\theta})}{v^T_m(e^{-i\theta})v_m(e^{i\theta})} =
p(\theta)
\end{equation}
and hence $\lambda_{\min}(P_m)\leq p(\theta)$. When $m \rightarrow \infty$
we obtain the desired result.
\end{proof}

\begin{lemma}\label{lem2}
\[
 \| P_m-R_m\| = O(m^{-\frac{1}{2}}).
\]
\end{lemma}

\begin{proof}
Consider
\[
P_m-R_m = \left[\begin{array}{ccccc}
0 & \frac{1}{m-1}p_1 & \frac{1}{m-2} p_2 \\
\frac{1}{m-1}p_1 & 0 & \frac{1}{m-1} p_1 \\
\frac{1}{m-2} p_2 & \frac{1}{m-1}p_1 & 0 \\
& & & \ddots \\
& & & & 0
\end{array}\right]
\]
and hence for the Froebenius norm
\[
\| P_m-R_m\|^2 = \sum_{k=1}^n \frac{m-k}{(m-k)^2}p^2_k = \sum_{k=1}^n \frac{1}{m-k} p^2_k.
\]
\end{proof}

We are now ready to state our main result.

\begin{theorem}\label{main_result}
\[
\lim_{m\rightarrow +\infty}\lambda_{\min}(P_m)=\min_\theta p(\theta).
\]
\end{theorem}

\begin{proof}
Let $v$ be an eigenvector  of $P_m$ such that  $v^Tv=1$ and $P_mv=\lambda_{\min}(P_m)v$. From
the equality
\[
v^TP_mv = v^T(P_m-R_m)v+v^TR_mv,
\]
we obtain with the help of Lemma \ref{lem2} the following inequality
\[
\lambda_{\min}(P_m)\geq O(m^{-\frac{1}{2}})+  \lambda_{\min}(R_m).
\]
Taking the limit, we obtain
\[
\liminf_{m\rightarrow +\infty}\lambda_{\min}(P_m)\geq\lim_{m\rightarrow +\infty}\lambda_{\min}(R_m).
\]
Using Lemma \ref{lem1} and Theorem \ref{Szego}, we can see that
\[
\liminf_{m\rightarrow +\infty}\lambda_{\min}(P_m)\geq \lim_{m\rightarrow +\infty}\lambda_{\min}(R_m)=\min_{\theta} p(\theta)
\]
and hence
\[
\liminf_{m\rightarrow +\infty}\lambda_{\min}(P_m)\geq \min_\theta p(\theta)\geq \limsup_{m\rightarrow +\infty}\lambda_{\min}(P_m).
\]
If $x_m$ is a real sequence then it is well-known that if $\liminf_{m\rightarrow +\infty}x_m=\limsup_{m\rightarrow +\infty}x_m$, then the sequence $x_m$ converges to
$\lim_{m\rightarrow +\infty}x_m=\liminf_{m\rightarrow +\infty}x_m=\limsup_{m\rightarrow +\infty}x_m$,
and this completes the proof.
\end{proof}

\begin{corollary}
Assume that polynomial $p$ is positive.
Then, there exists a sufficiently large integer $m_0$ such that for $m \geq m_0$,
the Toeplitz matrix $P_m$ is positive definite.
\end{corollary}

\begin{proof}
Use Theorem \ref{main_result}.
\end{proof}

\begin{remark}\label{rem1}
Note that when $p$ is positive,
matrices $P_m$ are not necessarily positive definite if $m$ is not large enough.
As a simple example consider the positive polynomial
$p(\theta)=2+2\cos\theta+\frac{8}{5}\cos2\theta$.
We have
\[
P_3=\left[\begin{array}{ccc}
2 & \frac{3}{2} &  \frac{12}{5}\\[.5em]
\frac{3}{2}   & 2  &  \frac{3}{2} \\[.5em]
\frac{12}{5} & \frac{3}{2}  & 2
\end{array}\right]
\]
which is not positive definite, since $\lambda_{\min}(P_3)= -\frac{2}{5}$.
Also, the next Toeplitz matrix
\[
P_4=\left[\begin{array}{cccc}
2 &  \frac{4}{3}   & \frac{8}{5}    &     0\\[.5em]
\frac{4}{3} &  2  &  \frac{4}{3}  &  \frac{8}{5}\\[.5em]
 \frac{8}{5} &   \frac{4}{3}   & 2 &   \frac{4}{3}\\[.5em]
 0  &   \frac{8}{5}  &  \frac{4}{3}  &  2
\end{array}\right],
\]
is not positive definite either, since $\lambda_{\min}(P_4)=\frac{8}{13}-\frac{2\sqrt{509}}{15} \approx -0.3415$.
However, one can check that when $m\geq m_0=30$, matrices
$P_m$ are indeed positive definite.
\end{remark}

\section{LMI inner approximations of stability domain}

Consider a monic polynomial
\[
d(z)=d_0+d_1z+\cdots+d_{n-1}z^{n-1}+z^n
\]
of degree $n$, with coefficient vector $d \in {\mathbb R}^n$
and let us define the set
\[
{\mathcal S} = \{d \in {\mathbb R}^n \: :\: d(z) \:\mathrm{stable} \}
\]
where stability is meant in the discrete-time, or Schur sense, i.e. all
the roots of $d(z)$ belong to the open unit disk. Many control problems
(e.g. fixed-order or robust controller design) can be formulated as
linear programming problems in $\mathcal S$. Unfortunately $\mathcal S$
is nonconvex when $n>2$, which renders controller design difficult
in general. It can therefore be relevant to describe convex inner
approximations of $\mathcal S$, in particular by exploiting the
modeling flexibility of linear matrix inequalities (LMIs),
see \cite{hsk03} and references therein.

An approach consists in choosing a monic polynomial
\[
c(z)=c_0+c_1z+\cdots+c_{n-1}z^{n-1}+z^n
\]
which is stable. Once $c$ is given, we define the trigonometric polynomial
\[
\begin{array}{rcl}
z=e^{i\theta} \mapsto p^{c,d}(\theta) & = &
c(z^{-1})d(z)+c(z)d(z^{-1})
\\
& = & 2\displaystyle\sum_{l=0}^n\sum_{\begin{subarray}{c}j,k=0\\
|j-k|=l\end{subarray}}^nc_jd_k\cos l\theta
\end{array}
\]
and the set
\[
{\mathcal P}^c = \{d \in {\mathbb R}^n \: :\: p^{c,d}(\theta) > 0
\quad\forall\:\theta \in {\mathbb R}\}.
\]

\begin{lemma}\label{schur}
Let $c(z)$ be a given stable polynomial. Then ${\mathcal P}^c \subset {\mathcal S}$.
\end{lemma}

\begin{proof}
A geometric proof is as follows. Since polynomial $c(z)$ is Schur stable,
when $z=e^{i\theta}$ varies along the unit circle,
complex number $c(e^{i\theta})$ has a net increase of argument of $2n\pi$,
or equivalently the plot of $c(e^{i\theta})$ encircles the origin $n$ times, see
e.g. \cite[Section 1.3.3]{bck} or use Cauchy's argument principle. Notice that
the real number $p^{c,d}(\theta)=c(e^{-i\theta})d(e^{i\theta})+c(e^{i\theta})d(e^{-i\theta})$
is equal to $2|c(e^{i\theta})d(e^{i\theta})|\cos(c(e^{i\theta}),d(e^{i\theta}))$
where the last term is the cosine of the oriented angle between vectors
$c(e^{i\theta})$ and $d(e^{i\theta})$ in the complex plane. Therefore
$p^{c,d}(\theta)$ positive implies that the cosine is positive and hence that
the angle between $c(e^{i\theta})$ and $d(e^{i\theta})$
is less than $\frac{\pi}{2}$ in absolute value for any given
value of $\theta$. This means
that complex number $d(e^{i\theta})$ also encircles the
origin $n$ times when $\theta$ range from $0$ to $2\pi$, and hence
that polynomial $d(z)$ is Schur stable.
\end{proof}

Let $P^{c,d}_m$ be the symmetric banded Toeplitz matrix
corresponding to polynomial $p^{c,d}$, built as in (\ref{pm}), and define the set
\[
{\mathcal P}^c_m = \{d \in {\mathbb R}^n \: :\: P^{c,d}_m \succ 0\}
\]
where $\succ 0$ means positive definite. Note that symmetric matrix $P^{c,d}_m$ depends
affinely on $d$, so that ${\mathcal P}^c_m$ is a convex LMI set.

\begin{theorem}\label{inner}
Let $c(z)$ be a given stable polynomial of degree $n$, and let $m>n$.
Then ${\mathcal P}^c_m \subset {\mathcal S}$.
\end{theorem}

\begin{proof}
Since $mp^{c,d}(\theta)=v^T_m(e^{-i\theta})P^{c,d}_mv_m(e^{i\theta})$,
positive definiteness of matrix $P^{c,d}_m$ implies positivity of
polynomial $p^{c,d}(\theta)$. Then use Lemma \ref{schur}.
\end{proof}

Set ${\mathcal P}^c_m$ is therefore a valid convex inner approximation
of the nonconvex stability region $\mathcal S$. Its geometry depends
only on the choice of a stable polynomial $c(z)$.

\begin{theorem}\label{limit}
Let $c(z)$ be a given stable polynomial. Then
${\mathcal P}^c = \lim_{m\rightarrow +\infty} {\mathcal P}^c_m$.
\end{theorem}

\begin{proof}
Use Theorem \ref{main_result}.
\end{proof}

Finally we make the connection with the results in \cite{hsk03}.
Recall that a discrete-time rational function is strictly
positive real (SPR) whenever its real part is strictly positive
when evaluated along the unit circle.

\begin{theorem}
\[
{\mathcal P}^c = \{d \in {\mathbb R}^n \: :\: \frac{d(z)}{c(z)}
\:\:\mathrm{SPR} \}.
\]
\end{theorem}

\begin{proof}
Since $c(z)$ is stable, the SPR inequality
\[
\mathrm{Re}\:\frac{d(e^{i\theta})}{c(e^{i\theta})} =
\frac{1}{2}\left(\frac{d(e^{i\theta})}{c(e^{i\theta})}+
\frac{d(e^{-i\theta})}{c(e^{-i\theta})}\right) =
\frac{c(e^{-i\theta})d(e^{i\theta})+c(e^{i\theta})d(e^{-i\theta})}
{2|c(e^{i\theta})|^2} > 0
\]
is equivalent to positivity of trigonometric polynomial $p^{c,d}(\theta)$.
\end{proof}

Polynomial $c(z)$ is referred to as a central polynomial in \cite{hsk03}
since set ${\mathcal P}^c$ is built around $c(z)$ in the coefficient
space. Note however that there is no guarantee that $c(z)$ belongs
to ${\mathcal P}^c_m$ if $m$ is not large enough, see Remark \ref{rem1}.

\section{Example}

\subsection{Second-order polynomials}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{lmi3}
\includegraphics[scale=0.8]{lmi4}
\caption{3-by-3 LMI set (shaded gray, left)
and 4-by-4 LMI set (shaded gray, right) within second-order discrete-time
stability region (triangle).\label{lmi34}}
\end{center}
\end{figure}

We consider second-order polynomials for which the exact stability region
is a triangle with vertices $(z+1)^2$, $(z-1)(z-1)$ and $(z-1)^2$
\cite[Example 11.13]{ackermann}.

Choosing $c(z)=z^2$, we have $p^{c,d}(\theta)=2+2d_1\cos\theta+2d_0\cos2\theta$.
The first LMI inner approximation is
\[
{\mathcal P}^{c,d}_3 = \{(d_0,d_1) \: :\: P^{c,d}_3 = \left[\begin{array}{ccc}
2 & \frac{3}{2}d_1 & 3d_0 \\
\frac{3}{2}d_1 & 2 & \frac{3}{2}d_1 \\
3d_0 & \frac{3}{2}d_1 & 2
\end{array}\right] \succ 0\}
\]
and it is represented on the left of Figure \ref{lmi34} within the stability
triangle, as claimed by Theorem \ref{inner}.

The second LMI inner approximation is
\[
{\mathcal P}^{c,d}_4 = \{(d_0,d_1) \: :\: P^{c,d}_4 = \left[\begin{array}{cccc}
2 & \frac{4}{3}d_1 & 2d_0 & 0\\
\frac{4}{3}d_1 & 2 & \frac{4}{3}d_1 & 2d_0\\
2d_0 & \frac{4}{3}d_1 & 2 & \frac{4}{3}d_1 \\
0 & 2d_0 & \frac{4}{3}d_1 & 2
\end{array}\right] \succ 0\},
\]
see the right of Figure \ref{lmi34}.

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{lmi7}
\includegraphics[scale=0.8]{lmi50}
\caption{7-by-7 LMI set (shaded gray, left)
and 50-by-50 LMI set (shaded gray, right) within second-order discrete-time
stability region (triangle).\label{lmi750}}
\end{center}
\end{figure}

On the left of Figure \ref{lmi750}
we represent the LMI set
\[
{\mathcal P}^{c,d}_7 = \{(d_0,d_1) \: :\: P^{c,d}_7 = \left[\begin{array}{ccccccc}
2 & \frac{7}{6}d_1 & \frac{7}{5}d_0 & 0 & 0 & 0 & 0\\
\frac{7}{6}d_1 & 2 & \frac{7}{6}d_1 & \frac{7}{5}d_0 & 0 & 0 & 0\\
\frac{7}{5}d_0 & \frac{7}{6}d_1 & 2 & \frac{7}{6}d_1 & \frac{7}{5}d_0 & 0 & 0 \\
0 & \frac{7}{5}d_0 & \frac{7}{6}d_1 & 2 & \frac{7}{6}d_1 & \frac{7}{5}d_0 & 0 \\
0 & 0 & \frac{7}{5}d_0 & \frac{7}{6}d_1 & 2 & \frac{7}{6}d_1 & \frac{7}{5}d_0 \\
0 & 0 & 0 & \frac{7}{5}d_0 & \frac{7}{6}d_1 & 2 & \frac{7}{6}d_1 \\
0 & 0 & 0 & 0 & \frac{7}{5}d_0 & \frac{7}{6}d_1 & 2
\end{array}\right] \succ 0\}.
\]
The boundary of this set
is piecewise polynomial, defined by two algebraic plane
curves whose irreducible defining polynomials $-7200 + 5040d_0 + 3528d_0^2
+ 4900d_1^2 - 5145d_0d_1^2$ (a cubic) and $6480000 + 4536000d_0 - 9525600d_0^2
- 8820000d_1^2 - 4445280d_0^3 + 7717500d_0d_1^2 + 3111696d_0^4
- 4321800d_0^2d_1^2 + 1500625d_1^4$ (a quartic)
factor the determinant of the 7-by-7 pencil $P^{c,d}_7$.
See Figure \ref{lmi7closure} for a representation of
this set and the algebraic components of its boundary.

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{lmi7closure}
\caption{7-by-7 LMI set (shaded gray)
and the algebraic components of its boundary (thick black lines).\label{lmi7closure}}
\end{center}
\end{figure}

On the right of Figure \ref{lmi750}
we represent the LMI set ${\mathcal P}^{c,d}_{50}$
which, according to Theorem \ref{limit},
is almost equal to the lifted LMI set
\[
{\mathcal P}^{c,d} =
\{(d_0,d_1) \: :\:\exists\:(q_0,q_1,q_2) \: :\:
\left[\begin{array}{ccc}
q_0 & q_1 & d_0 \\
q_1 & q_2-q_0 & d_1-q_1 \\
d_0 & d_1-q_1 & 2-q_2
\end{array}\right] \succ 0\},
\]
the projection onto ${\mathbb R}^2$ of an LMI living
in ${\mathbb R}^5$, and which is the union of an ellipse and a triangle,
as studied in \cite{hsk03}.

\subsection{Third order}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.6]{spacelmi4}
\includegraphics[scale=0.6]{spacelmi50}
\caption{4-by-4 LMI set (shaded gray, left)
and 50-by-50 LMI set (shaded gray, right) within third-order discrete-time
stability region (delimited by a meshed hyperbolic parabolic embedded in a
tetrahedron).\label{spacelmi}}
\end{center}
\end{figure}

We consider third-order polynomials for which the exact stability region
is delimited by a nonconvex hyperbolic parabolic embedded in a tetrahedron
with vertices $(z+1)^3$, $(z+1)^2(z-1)$, $(z+1)(z-1)^2$ and $(z-1)^3$,
see \cite[Example 11.14]{ackermann}.

Choosing $c(z)=z^3$, we have $p^{c,d}(\theta)=2+2d_2\cos\theta+2d_1\cos2\theta+2d_0\cos3\theta$.
The first LMI inner approximation is
\[
{\mathcal P}^{c,d}_4 = \{(d_0,d_1,d_2) \: :\: P^{c,d}_4 = \left[\begin{array}{cccc}
2 & \frac{4}{3}d_2 & 2d_1 & 4d_0 \\
\frac{4}{3}d_2 & 2 & \frac{4}{3}d_2 & 2d_1 \\
2d_1 & \frac{4}{3}d_2 & 2 & \frac{4}{3}d_2 \\
4d_0 & 2d_1 & \frac{4}{3}d_2 & 2
\end{array}\right] \succ 0\}
\]
and it is represented on the left of Figure \ref{spacelmi} within the nonconvex stability
region, as claimed by Theorem \ref{inner}. On the right of Figure \ref{spacelmi}
is represented the LMI set ${\mathcal P}^{c,d}_{50}$
which, according to Theorem \ref{limit}, is almost equal to the lifted LMI set
${\mathcal P}^{c,d}$.

\section{Concluding Remarks}

We have used results on spectra of Toeplitz matrices to construct a hierarchy
of convex inner approximations of the nonconvex set of stable polynomials,
with potential applications in fixed-order robust controller design.
The main difference with respect to previous results is that the
inner sets are defined by LMIs (affine sections of the
cone of positive definite matrices) without the need to resort
to projections and lifting variables. Moreover, our LMI sets
belong to a hierarchy converging asymptotically to a lifted LMI
inner approximation described previously in \cite{hsk03}.

It is likely that our results can be extended to deal with
positive trigonometric polynomial matrices and block Toeplitz matrices,
with potential applications in multi-input multi-output control systems.

Sufficient conditions ensuring that a real polynomial is a sum-of-squares
(and hence that it is positive) have been proposed in \cite{lasserre},
so it could be insightful to transpose these conditions to trigonometric
polynomials and compare with our approach. Results in \cite{lasserre}
are also valid for multivariate polynomials, and this may have applications
in fixed-order or robust controller design for multi-dimensional systems.

\section*{Acknowledgements}

The first author is supported by a Ram\'on y Cajal grant from the
Spanish government. The second author acknowledges support by
project No.~103/10/0628 of the Grant Agency of the Czech Republic.

config: arxiv


TITLE: Which of following subgroups of $G$ are normal?
QUESTION [0 upvotes]: For real numbers $a$ and $b$, define a mapping $g_{a,b}\colon \mathbb R \to \mathbb R$ by $g_{a,b}(x)=ax+b$.
Let $G = \{g_{a,b}\mid a,b \in R, a\neq0\}$.
Under composition of mappings this becomes a group. Which of following subgroups of $G$ are normal?

$H=\{g_{a,b}\mid a\neq0,a\in Q, b \in \mathbb R\}$
$H=\{g_{a,b}\mid b \in \mathbb R\}$
$H=\{g_{a,b}\mid b \in \mathbb Q\}$

How do I do this? Thanks.

REPLY [2 votes]: This is how you do this problem: You start by taking the first subgroup, $H_1$, and take an arbitrary $h_{a, b}$ inside that subgroup, take an arbitrary $g_{c, d} \in G$, and find the concrete expression for the composited transformation $g_{c, d}h_{a, b}g_{c, d}^{-1}$. You then need to decide whether this new element will always be an element if $H_1$, no matter what $a, b, c, d$ are (except that $a \in \Bbb Q$, since $h_{a, b} \in H_1$, and $a,c \neq 0$, of course).
If it is always an element of $H_1$, then $H_1$ is normal. You will need to present some kind of reasoning for why this must be true. If you're lucky, it will be evident just from the concrete expression of $g_{c, d}h_{a, b}g_{c, d}^{-1}$. If there is even one single choice of $a, b, c, d$ (still with the restriction to $a$ and $c$) that makes $g_{c, d}h_{a, b}g_{c, d}^{-1} \notin H_1$, then $H_1$ is not normal. Putting forth such $a, b, c, d$ is enough proof for that.
Then you do the same thing for $H_2$ and $H_3$.

REPLY [1 votes]: For the subgroup $H=\{g_{a,b}\:|\:a\neq 0,\:a\in\mathbb{Q},\:b\in\mathbb{R}\}$ to be normal, we would need that
\begin{equation}
g^{-1}hg\in H
\end{equation}
for every $g\in G$.
So let's do this:
\begin{equation}
q(x)=\frac{(x-b)}{a}\circ (cx+d)\circ (a'x+b')\qquad\qquad a,a',b,b',d\in\mathbb{R}\qquad c\in\mathbb{Q}
\end{equation}
We need to check if $q(x)\in H$. Solving we get
\begin{equation}
q(x)=a'\Big(c\cdot \frac{(x-b)}{a}+d\Big)+b'= \frac{a'c}{a}x+\text{real term}.
\end{equation}
Well, if $c\in\mathbb{Q}$, and $a,a'\in\mathbb{R}$, is it true that $\frac{a'c}{a}\in\mathbb{Q}$? You can do something similar for the other ones.
Btw I forgot to mention that the denominators on fractions and $a,a'$ are $\neq 0$ but this is obvious.
Also, I think that you should first do some computations with composition of these "affine functions" to get some grasp on what compositions look like and what inverses look like (which I implictly used in the answer above).


TITLE: Asymptotic expansion of $\sum _{k=1}^n \left(\frac{k}{n}\right)^k$
QUESTION [4 upvotes]: How to calculate the asymptotic expansion of these two sums w.r.t $n$ to arbitrary precision?

$$\sum _{k=1}^n \left(\frac{k}{n}\right)^k,\sum _{k=1}^n \Gamma\left(\frac{k}{n}\right)^{-k}$$

According to O.Furdui's problem book Limits, Series and fractional part integrals it might be a open problem. I have no idea other than knowing the first sum tends to $\frac{e}{e-1}$ as $n\rightarrow \infty$ (Tannery theorem, for instance) and would like you to help. Note that similar sums $\small\sum\limits _{k=1}^n \left(\frac{k}{n}\right)^n$, $\small\sum\limits _{k=1}^n \Gamma\left(\frac{k}{n}\right)^{-n}$ can be approximated using Taylor expansion but not so helpful for this case. Thanks in advance!

REPLY [3 votes]: Since @Diger's answer captures the main idea, this answer merely amends it to cover the case of $\Gamma$, and provides some computations. First let's restate the result: for $n\to\infty$ $$\sum_{k=1}^{n}(k/n)^k\asymp A_0+\sum_{j=1}^{(\infty)}(j^j+A_j)n^{-j},\qquad A_j=\sum_{k=0}^{\infty}a_j(k),$$ where $a_j(k)$ are the expansion coefficients of $(1-k/n)^{n-k}$ in powers of $1/n$ (for fixed $k$): $$\sum_{j=0}^{\infty}a_j(k)x^j:=(1-kx)^{(1-kx)/x}=\exp\left[-k\left(1-\sum_{j=1}^\infty\frac{(kx)^j}{j(j+1)}\right)\right].$$
Similarly, the contribution to the asymptotics of $$\sum_{k=1}^{n}\big(\Gamma(k/n)\big)^{-k}\asymp\sum_{j=0}^{(\infty)}B_j n^{-j},$$ up to $n^{-j}$, is the one from the first $j$ terms of the defining sum, plus the one from a handful of the last terms, with the "handful" tending to infinity. Explicitly, $B_j=\sum_{k=1}^{j}b_j(k)+\sum_{k=0}^{\infty}c_j(k)$, where $$\big(\Gamma(kx)\big)^{-k}=:\sum_{j=k}^{\infty}b_j(k)x^j,\qquad\big(\Gamma(1-kx)\big)^{-(1-kx)/x}=:\sum_{j=0}^{\infty}c_j(k)x^j.$$ For computations, we use the known expansion $$\log\Gamma(1-x)=\gamma x+\sum_{j=2}^{\infty}\frac{\zeta(j)}{j}x^j$$ from which one deduces $1/\Gamma(x)=\sum_{j=1}^{\infty}g_j x^j$ with $$g_1=1,\quad j g_{j+1}=\gamma g_j-\sum_{k=2}^j(-1)^k\zeta(k)g_{j-k+1}.$$

The first few values of $a_j(k)$ are
\begin{align*}
  a_0(k)&=e^{-k}
\\a_1(k)&=\frac{e^{-k}}{2}     k^2
\\a_2(k)&=\frac{e^{-k}}{24}   (3 k^4 + 4 k^3)
\\a_3(k)&=\frac{e^{-k}}{48}   (k^6 + 4 k^5 + 4 k^4)
\end{align*}
The corresponding values of $A_j$ are then
\begin{align*}
  A_0&=\frac{e}{e-1}
\\A_1&=\frac{e(e + 1)}{2(e-1)^3}
\\A_2&=\frac{e(7 e^3 + 45 e^2 + 21 e - 1)}{24(e-1)^5}
\\A_3&=\frac{e(9 e^5 + 193 e^4 + 422 e^3 + 102 e^2 - 7 e + 1)}{48(e-1)^7}
\end{align*}
Denoting $c:=e^\gamma$, the first three values of $B_j$ are
\begin{align*}
B_0&=\frac{c}{c-1},
\\B_1&=1-\left(\frac{\pi^2}{12}-\gamma\right)\frac{c(c+1)}{(c-1)^3},
\\B_2&=4+\gamma+\frac{c}{(c-1)^5}
\\&\times\left[\left(\frac{\pi^2}{12}-\frac{\zeta(3)}{3}\right)(c^3+3c^2-3c-1)\right.
\\&+\left.\frac{1}{2}\left(\frac{\pi^2}{12}-\gamma\right)^2(c^3+11c^2+11c+1)\right].
\end{align*}
[The expression for $B_3$ looks too cumbersome to put here.]


TITLE: Inertial Frames in Special Relativity
QUESTION [1 upvotes]: According to the postulates of special relativity, all inertial frames are equal in all respects. Then how does it follow from this, that the space is isotropic and homogenous for an inertial frame and time is homogenous. Or does the former follow from the latter?
Or are they two independent postulates about inertial frames? Can isotropy and homogeneity of space and homogeneity of time for an inertial frame follow from a perhaps even more fundamental postulate in physics?

REPLY [2 votes]: Let us start from classical physics.
The fundamental invariance postulate in classical physics is that all physical laws describing an isolated physical system in an inertial reference frame are invariant in form under the action of Galileian (Lie) group. That group is made of $4$ (Lie) subgroups.
(1) spatial translations, invariance under space translations is also known as spatial homogeneity in a given inertial reference frame. It implies that the total momentum of the system is conserved along its the evolution.
(2) spatial  rotations, invariance under space translations is also known as spatial isotropy  in a given inertial reference frame.
It implies that the total angular momentum of the system is conserved along its the evolution.
(3) temporal translations, invariance under time translations is also known as temporal homogeneity in a given inertial reference frame.
It implies that the total energy of the system is conserved along its the evolution.
(4) subgroup of pure Galileian transformations ($t\to t'=t$, ${\bf x} \to {\bf x}' = {\bf x} + t{\bf v}$).
This last type of invariance also implies physical equivalence of all inertial reference frames. It implies the existence of a relation connecting  the total momentum of the system and the motion of the center of mass.
In special relativistic physics, passing to deal with Poincaré group in place of Galileo group, the situation is almost identical. It is certainly identical regarding (1), (2) and (3) as the mentioned groups of transformations are also subgroups of Poincaré group.
The only relevant difference concerns (4). Here the subgroup of pure Galileian transformation is replaced with the set of pure Lorentz transformations: the boosts. Invariance under boost implies again physical equivalence of all inertial reference frames. The associated conservation law is a theorem analogous to the classical one, with the fundamental difference that now the total mass of the system includes the contribution of energies of the parts of the system in accordance with $m=E/c^2$.


TITLE: Why is $F^*(\mathcal L) = \mathcal L^{\otimes p}$ where $F$ is the absolute Frobenius and $\mathcal L$ is an invertible sheaf?
QUESTION [13 upvotes]: Suppose $S$ is such that $\mathcal O_S$ is killed by multiplication by $p$. The absolute Frobenius $F: S \to S$ is defined to be be the identity on the underlying points topological space of $S$, with the sheaf map $F^\#: \mathcal O_S \to \mathcal O_S$ given by $x \mapsto x^p$ for any section.
The pullback sheaf is defined to be
$$F^*(\mathcal L) = F^{-1} L \otimes_{F^{-1}\mathcal O_S} \mathcal O_S$$
Where $F^{-1} \mathcal L$ is the sheafification of the presheaf defined by
$$U \mapsto \lim_{F(V)\supset U}  \mathcal L (V)$$
But since $F$ is the identity on the underlying space, won't we have $F^{-1} \mathcal L = \mathcal L$ and $F^{-1} \mathcal O_S$ = $\mathcal O_S$, and hence $F^* \mathcal L = \mathcal L$? I can't see how to bring $F^\#$ into the calculation.
I know the intuitive answer is that the transition functions are sent to their p-th powers. But I can't work out the details.

REPLY [5 votes]: Even more simple, and more general:

Let $S$ be a ringed space of $\mathbb{F}_p$-algebras, and let $F : S \to S$ be the absolute Frobenius. Then for every line bundle $\mathcal{L}$ on $S$ we have $F^* \mathcal{L} \cong \mathcal{L}^{\otimes p}$.

Proof. Since $F^*$ is left adjoint to $F_*$ (which could be seen as a definition), for every sheaf of modules $M$ on $S$ we have to prove $\hom(\mathcal{L},F_* M) \cong \hom(\mathcal{L}^{\otimes p},M)$, naturally in $M$. For $\mathcal{L}=\mathcal{O}_S$ this is trivial, both sides identify with $\Gamma(M)$, and in general $\mathcal{L}$ looks locally like this. So we only have to observe that the isomorphisms glue, i.e. that for every isomorphism $\gamma : \mathcal{O}_S \to \mathcal{O}_S$ resp. unit $\gamma \in \Gamma(\mathcal{O}_S)^*$ the diagram
$$\begin{matrix}
\hom(\mathcal{O}_S,F_* M) & \cong & \Gamma(F_* M) & = & \Gamma(M) & \cong & \hom(\mathcal{O}_S^{\otimes p},M) \\
\gamma^* \downarrow  ~ & & ~ \downarrow \cdot \gamma ~ & & ~ \downarrow \cdot \gamma^p & & ~ \downarrow (\gamma^{\otimes p})^* \\\hom(\mathcal{O}_S,F_* M) & \cong & \Gamma(F_* M) & = & \Gamma(M) & \cong & \hom(\mathcal{O}_S^{\otimes p},M)
\end{matrix}$$
commutes, which can be checked directly by the definition of $F$.


TITLE: Prove that $\binom{m+n}{m}=\sum\limits_{i=0}^m \binom{m}{i}\binom{n}{i}$
QUESTION [2 upvotes]: I need to proof this following equality :
$$\binom{m+n}{m}=\sum_{i=0}^m \left(\binom{m}{i}\binom{n}{i}\right)$$
This is what I did combinatoric proof:
Left : subset with $m$ members from $m+n$
Right : $\binom{m}{i} \rightarrow$ The number of subsets in set $m$ could also be written as $2^m$ AND $\binom{n}{i} \rightarrow$ the number of subsets with $m$ members from set $n$
In case $ n \leq m \implies \binom{n}{i}=2^n$
So this is what I came up with I still can't see why those expression are equal.
Any ideas? Thanks.

REPLY [1 votes]: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
\begin{align}
\sum_{k = 0}^{m}{m \choose k}{n \choose k} & =
\sum_{k = 0}^{m}{m \choose k}{n \choose n - k} =
\sum_{k = 0}^{m}{m \choose k}\ \overbrace{\oint_{\verts{z} = 1}
{\pars{1 + z}^{n} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic}}
^{\ds{{n \choose n - k}}}
\\[3mm] & =
\oint_{\verts{z} = 1}
{\pars{1 + z}^{n} \over z^{n + 1}}\
\overbrace{\sum_{k = 0}^{m}{m \choose k}z^{k}}^{\ds{\pars{1 + z}^{m}}}\
\,{\dd z \over 2\pi\ic} =
\oint_{\verts{z} = 1}{\pars{1 + z}^{m + n} \over z^{n + 1}}
\,{\dd z \over 2\pi\ic} = \color{#f00}{{m + n \choose n}}
\end{align}


TITLE: Unable to understand correlation coefficient / auto correlation
QUESTION [1 upvotes]: Suppose I have a vector say:
[5 5 5 5 4 5]
then common sense says that there is a very high auto-correlation for the vector because it is more or less the same values.
But when I try to calculate the auto-correlation coefficient, I'm getting a very low value(<0.3) for all lags. What does this mean? shouldn't it be higher because the series is very similar?
Am I missing something?
does correlatiom mean not similarity but similarity in rate(Rate of change)?

REPLY [2 votes]: A similar situation arises when you fit a regression line to perfectly horizontal data — you get a “linear” relationship that is nearly perfect but also completely uninformative.
Correlation measures how changes in X about its mean are related to changes in Y about its mean. In the case where one of the variables is (or is almost) constant, then there isn’t much variation left to attribute to the other variable:


TITLE: Finding region of integration
QUESTION [1 upvotes]: Integrate$
\int\int\exp(\frac{x^{2}+y^{2}}{2})\text{d}x\text{d}y $  over  region R, bound by lines, $y=0, y=x$ and arcs of circles $x^{2}+y^{2}=1$ and $x^{2}+y^{2}=2$.
I could plot the above equatons on an $x-y$ plane. But couldn't find a common region since  they are not given in form if inequalities. How do I find the region of integration?

REPLY [0 votes]: There are four possible regions. The first one lies in the first quadrant, the second one lies in the first and second quadrant, the third one lies in the third quadrant and the fourth lies in the third and fourth quadrant. All of them are sectors of a ring formed by the two bounding circles.


TITLE: $(2p-x-y)^2 = 4xy+1$ and $2p-x-y = 2m+1$
QUESTION [0 upvotes]: Let $x,y,p,$ and $m$ be positive integers such that $(2p-x-y)^2 = 4xy+1$ and $2p-x-y = 2m+1$. Prove that if $m = dh$ and $x = dk$ where $d = \gcd(m,x)$, then $m+1 = gk$ and $y = gh$ where $g = \gcd(m+1,y)$.

This seemed like a complicated statement to prove and so I wasn't sure how to go about proving  it. Would proving it by contradiction work or is there an easier way?

REPLY [1 votes]: Hint:
From first two identities, you have
\begin{align*}
(2p-x-y)^2 &=(2m+1)^2 \\
&=4m^2+4m+1\\
&=4xy+1
\end{align*}
So you have $m^2+m=xy$. Then you can write:
\begin{align*}
m^2+m &= xy \\
(m+1)dh &= dky \\
(m+1)h &= ky
\end{align*}
Therefore you have $\frac{m+1}{y} = \frac{k}{h}$ where $h,k$ are relatively prime. Hence you should have
$$
m+1 = \gcd(m+1,y)k, \quad y = \gcd(m+1,y)h
$$


TITLE: Geometry: Find the radius of a circle given parallel secants
QUESTION [3 upvotes]: Suppose a circle has two parallel chords of lengths $a$ and  $b$, and the chords are separated by a distance of $c$. Using only the usual high school geometry theorems (i.e. no trig or calculus), can we derive a formula for the radius?
I've tried drawing radii in several places without making useful progress. I can't see how to find the radius intersecting the circle and a chord. I can draw the segment from one chord-circle intersection to another, but it need not pass through the center so I can't leverage this to get the radius.

REPLY [1 votes]: I just answered this question in chat, so I thought it would be worth posting the answer here.

The horizontal position of a vertical chord of length $c$ in a circle of radius $r$ would be $\pm\sqrt{r^2-\frac{c^2}4}$.
Thus, the distance, $d$, between chords of length $c_1$ and $c_2$ (with $c_1\ge c_2$) would be
$$
d=\sqrt{r^2-\tfrac{c_2^2}4}\pm\sqrt{r^2-\tfrac{c_1^2}4}\tag1
$$
The "$\pm$" depends on whether or not the chords appear on the same side of the center of the circle. In either case, we have
$$
\frac{c_1^2-c_2^2}{4d}=\sqrt{r^2-\tfrac{c_2^2}4}\mp\sqrt{r^2-\tfrac{c_1^2}4}\tag2
$$
To verify $(2)$, simply multiply $(1)$ and $(2)$.
Average $(1)$ and $(2)$ to get
$$
\frac{c_1^2-c_2^2+4d^2}{8d}=\sqrt{r^2-\tfrac{c_2^2}4}\tag3
$$
Thus,
$$
\begin{align}
r^2
&=\frac{\left(c_1^2-c_2^2+4d^2\right)^2+16c_2^2d^2}{64d^2}\tag{4a}\\
&=\frac{c_1^4+c_2^4+16d^4-2c_1^2c_2^2+8c_1^2d^2+8c_2^2d^2}{64d^2}\tag{4b}\\
&=\frac{\left(c_1^2+c_2^2\right)^2+8\left(c_2^2+c_1^2\right)d^2+16d^4-4c_1^2c_2^2}{64d^2}\tag{4c}\\
&=\frac{\left(c_1^2+c_2^2+4d^2\right)^2-4c_1^2c_2^2}{64d^2}\tag{4d}\\
&=\frac{\left((c_1+c_2)^2+4d^2\right)\left((c_1-c_2)^2+4d^2\right)}{64d^2}\tag{4e}
\end{align}
$$
Explanation:
$\text{(4a):}$ solve $(3)$ for $r^2$
$\text{(4b):}$ expand
$\text{(4c):}$ collect
$\text{(4d):}$ collect
$\text{(4e):}$ apply $a^2-b^2=(a+b)(a-b)$
Therefore,
$$
r=\frac{\sqrt{\left((c_1+c_2)^2+4d^2\right)\left((c_1-c_2)^2+4d^2\right)}}{8d}\tag5
$$
In $(5)$, it doesn't matter whether $c_1\ge c_2$ or not.


TITLE: Positioning a member of an interval partition
QUESTION [1 upvotes]: Let $\ 0<\Lambda_1\le\ldots\le\Lambda_n\ $ be a finite non-decreasing sequence of positive reals, of length $\ n>0.\ $ Let
$$ D:=\sum_{k=1}^n \Lambda_k $$
The question is about the conditions which
allows to shift the interval $\ [0;\Lambda_k)\ $ over arbitrary
$\ x\in[0;D)\ $ by applying a permutation
$\ \pi:\{1\ldots n\}\rightarrow\{1\ldots n\}\ $ to the members
$\ [0;\Lambda_k)\ $ of partition $\ [0;D).\ $ The following simple theorem will provide the picture, then I will reformulate my question in a precise way.

Notation: $\ \mathbb S(n)\ $ is the symmetric group (of all permutations of $\ \{1\cdots n\}),\ $ and the union of the $n$
  half_closed-half_open intervals (for $k=1\ldots n$)
$$ L(\pi\ k)\ :=\ \left[\sum_{t=1}^{\pi(k)-1}\Lambda_{\pi(t)};
                          \sum_{t=1}^{\pi(k)}\Lambda_{\pi(t)} \right)$$
  partitions $\ [0;D)\ $ for every $\ \pi\in\mathbb S(n)$.

THEOREM 1
$$ [0;D)\ =\ \bigcup_{\pi\in\mathbb S(n)} L(\pi\ n)$$

Remark: It is essential to have here intervals for $\ k=n.\ $
  In general, the above theorem doesn't hold for $\ k<n,\ $ i.e. when
  $\ \Lambda_k\ <\ \max_{t=1\ldots n} \Lambda_t$.

QUESTION   What is the necessary and/or sufficient condition for
$$ [0;D)\ =\ \bigcup_{\pi\in\mathbb S(n)} L(\pi\ k)$$
This question is still a shorthand for several related questions, be it
about a single index $k$ or about a group of them.
Example 1   If $\ \Lambda_n>\frac D2\ $ then the answer to the Question is NO for every $ k<n;\ $ indeed, for such $k,\ $ no permutation can shift $\ [0;\Lambda_k)\ $ over $\ \frac D2$.
More generally,
if
$\ 2\cdot s<n\ $ and $\ \sum_{t=n-2\cdot s}^{n-s}\Lambda_t\ >\ \frac D2\ $
then the answer to Question is NO for every $k<n-2\!\cdot\! s$.

Backround The above theorem 1 was motivated and serves me as a step (tiny but essential) in my study of Egyptian sums.

REPLY [0 votes]: At the other end of the above statements, if $\ n>1\ $ and
$\ \Lambda_1<\Lambda_2\ $ then the answer is NO for $\ k=1:$
THEOREM 2   Let $\ n>1.\ $ Then
$$ \bigcup_{\pi\in\mathbb S(n)} L(\pi\ 1)\,\ \subseteq
   \,\ [0;\Lambda_1)\,\cup\,[\Lambda_2;D-\Lambda_2)\,\cup\,
    [\Lambda_n-\Lambda_1;D) $$
We see that $\,\ [0;D)\,\ne\,\bigcup_{\pi\in\mathbb S(n)} L(\pi\ 1)\,\ $
when $\ \Lambda_1<\Lambda_2\ $ since the non-empty intervals
$\ [\Lambda_1;\Lambda_2)\ $ and
$\ [D-\Lambda_n-\Lambda_2;\ D-\Lambda_n-\Lambda_1)\ $ are totally
ommitted.
More generally,
THEOREM 3
$$ \bigcup_{\pi\in\mathbb S(n)} L(\pi\ r)\,\ \subseteq
   \,\ \left[0;\sum_{k=1}^s\Lambda_k\right)\ \cup
   \ [\Lambda_{s+1};\ D-\Lambda_{s+1})\ \cup
   \ \left[D-\sum_{k=1}^s\Lambda_k;\ D\right) $$
where $\ r\le s<n$. Thus, the answer is NO for every $\ r\le s\ $ whenever
$$ \sum_{k=1}^s\Lambda_k\ <\ \Lambda_{s+1} $$
And a positive theorem follows,
THEOREM 4   If $\ \Lambda_n\le\frac D2\ $ and $\ n>1\ $ then the answer is  YES  for $\ n-1,\ $ and moreover
$$ \bigcup_{\pi\in\mathbb S(n)} L(\pi\,\ n\!-\!1)\,
   \ =\,\ [0;D)\ \quad\Leftarrow:\Rightarrow\quad\ \Lambda_n\,\le\,\frac D2 $$
Finally, more generally (once again),
THEOREM 5 If $\ 1\le s < n,\ $ and
$\ \sum_{k=1}^s\Lambda_k\ge\frac D2\,\ $ then the answer is  YES
for every $\ u=s\ldots n,\ $ i.e.
$$  \bigcup_{\pi\in\mathbb S(n)} L(\pi\,\ u)\,
   \ =\,\ [0;D) $$


TITLE: Prove $\iiint_{\mathbb{R}^3}\left ( \frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}+\frac{\partial f}{\partial z} \right) dxdydz=0$
QUESTION [2 upvotes]: Assume $f(x,y,z)$ is continuously differentiable on $\mathbb R^3$, and both the integral
$$
\iiint_{\mathbb{R}^3}{\left| f\left( x,y,z \right) \right|\text{d}}x\text{d}y\text{d}z
$$
and
$$
\iiint_{\mathbb{R}^3}{\left( \frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}+\frac{\partial f}{\partial z} \right) \text{d}}x\text{d}y\text{d}z
$$
exists. Prove that
$$\iiint_{\mathbb{R}^3}{\left( \frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}+\frac{\partial f}{\partial z} \right) \text{d}}x\text{d}y\text{d}z=0$$
I don't have any ideas about the problem. Can anyone help?

REPLY [2 votes]: Let $\mathcal{C}_r = [-r,r]^3$ denote the cube of side length $2r$ centered at $0$. Then
\begin{align*}
\left| \int_{\mathcal{C}_r} \frac{\partial f}{\partial x} \, \mathrm{d}x\mathrm{d}y\mathrm{d}z \right|
&= \left| \int_{[-r,r]^2} \left( f(r, y, z) - f(-r, y, z) \right) \, \mathrm{d}y\mathrm{d}z \right| \\
&\leq \int_{\partial\mathcal{C}_r \cap \{x=\pm r\}} \left| f(\mathbf{x}) \right| \, \sigma(\mathrm{d}\mathbf{x}),
\end{align*}
where $\sigma$ is the surface measure on $\partial\mathcal{C}_r$. Since similar results hold along the other coordinate directions, we have
\begin{align*}
\left| \int_{\mathcal{C}_r} \left(\frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}+\frac{\partial f}{\partial z}\right) \, \mathrm{d}x\mathrm{d}y\mathrm{d}z \right|
&\leq f(r), \qquad\text{where} \quad f(r) := \int_{\partial\mathcal{C}_r} \left| f(\mathbf{x}) \right| \, \sigma(\mathrm{d}\mathbf{x}).
\end{align*}
However, since
$$ \int_{0}^{\infty} f(r) \, \mathrm{d}r
= \int_{\mathbb{R}^3} \left| f(\mathbf{x}) \right| \, \mathrm{d}x\mathrm{d}y\mathrm{d}z
< \infty, $$
we have $\liminf_{r\to\infty} f(r) = 0$ and hence there exists a sequence $(r_n)_{n\geq 1}$ with $r_n \to \infty$ such that $f(r_n) \to 0$ as $n\to\infty$. From this, we obtain
$$ \left| \int_{\mathbb{R}^3} \left(\frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}+\frac{\partial f}{\partial z}\right) \, \mathrm{d}x\mathrm{d}y\mathrm{d}z \right|
= \lim_{n\to\infty} \left| \int_{\mathcal{C}_{r_n}} \left(\frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}+\frac{\partial f}{\partial z}\right) \, \mathrm{d}x\mathrm{d}y\mathrm{d}z \right|
\leq 0 $$
and therefore the desired conclusion follows.


TITLE: Find $f(c)$ given the graph of $f'(x)$
QUESTION [4 upvotes]: I am given a graph of the derivative of some function and asked to find $f(c)$.
I can't explain it well without the graph, so here is the image of the problem:

First of all, should't the point labeled on the graph as $(3,2)$ be $(2,3)$?
Second, wouldn't $f(6)$ be the integral from $0$ to $6$ of the graph?
If so, then I have the area of the square $(3*2)$ plus the first triangle $(3)$ minus the third triangle $(1)$, giving me an answer of $8$.
Is this incorrect?  Why do I need to know that $f(0)=7$?

REPLY [6 votes]: By the fundamental theorem of calculus:$$\int_0^6f'(x)\ \mathrm{d}x=f(6)-f(0)$$ So $f(6)=\int_0^6f'(x)\ \mathrm{d}x+f(0)$. To find the integral we must find the area above the x-axis and the curve and subtract the area below the x-axis and the curve. $$\int_0^6f'(x)\ \mathrm{d}x=6+3-1=8$$ So $f(6)=8+7=15.$

REPLY [1 votes]: Hint: By the fundamental theorem of calculus, we have
$$
\int_a^b f'(x)\,dx = f(b) \color{red}{- f(a)}
$$


TITLE: Why should there be a node at the walls of a standing wave
QUESTION [0 upvotes]: I can understand that if its a string, then since it is tired there should be a node. Also, for sound waves, since the particle near the wall cannot oscillate, there should be a node. But, in electromagnetic waves, it just has a varying electric and magnetic field. Why it should form a node at the walls ( like in radiation in a cavity)

REPLY [0 votes]: Because at wall electric field and magnetic field becomes will pass through inter space between molecules so it make node with low amplitude


TITLE: Euler method with infinite gradient at initial value
QUESTION [1 upvotes]: The title itself is self explanatory - I am trying to numerically solve an ODE with an initial value that has an infinite gradient. It seemed problematic to me and I am not certain as to how I should approach this.
e.g. $\frac {dy}{dx} = \frac y{\sqrt x} , y(0)=1$
(Obviously this can be solved analytically but I would like to know if there is any numerical method that tackles problems like this)
Thank you very much!

REPLY [0 votes]: Others can probably give a more "conventional" approach but one thing you can do, because $y'(x)$ is independent of $y(x)$, is take the following approach for the first step (at least).
For the initial slope think rather angle. You want to proceed with a certain angle but you can't use $\theta_1=\frac{\pi}{2}$... which is obviously no good.
Instead take as angle the mid-angle of $\theta_1=\pi/2$ and the angle of the curve at $x=h$:
$$\theta_2:=\tan^{-1}\left(y'(h)\right)=\tan^{-1}\left(\frac{1}{\sqrt{h}}\right),$$
and so take as initial angle:
$$\theta_0=\frac{\theta_1+\theta_2}{2}=\frac{\frac{\pi}{2}+\tan^{-1}\left(\frac{1}{\sqrt{h}}\right)}{2},$$
and so an initial slope of:
$$m_0:=\tan(\theta_0).$$
From here you can do normal Euler or perhaps keep it going with slope
$$m_k=\frac{y'(x_k)+y'(x_{k+1})}{2}.$$
This is an adaptation of Heun's Method. With a step-size of $h=0.1$ this gives an error for $y_1\approx y(x_1)$ of the order of $0.015$.