text:
\begin{document}

\title[Bounded Ratios over Positive Definite Matrices]{Bounded Ratios of Products
of Principal Minors of Positive Definite Matrices}
\author{H. Tracy Hall}
\address{Department of Mathematics \\
Brigham Young University\\
Provo, UT  84602}
\email{h.tracy@gmail.com}

\author{Charles R. Johnson}
\address{Department of Mathematics \\
 College of William and Mary \\
 Williamsburg, VA  23185}
\email{crjohnso@math.wm.edu}

\subjclass{Primary 15A45; Secondary 15A15, 15A48, 05B35}
\keywords{Determinantal inequality, bounded ratio, matrix, positive definite, positive semidefinite, principal minor,
multiplicative semigroup, cone of inequalities,
rank type, nullity type, asymptotic nullity type, matroid, face volume inequality}

\begin{abstract}
Considered is the multiplicative semigroup of ratios of products of principal
minors bounded over all positive definite matrices.
A long history of literature identifies various elements
of this semigroup, all of which lie in a sub-semigroup
generated by Hadamard-Fischer inequalities.  Via cone-theoretic
techniques and the patterns of nullity among positive
semidefinite matrices, a semigroup containing all bounded
ratios is given.  This allows the complete determination
of the semigroup of bounded ratios for $4$-by-$4$ positive definite
matrices, whose $46$ generators include
ratios not implied by Hadamard-Fischer and ratios
not bounded by $1$.
For $n \ge 5$ it is shown that the containment of semigroups
is strict, but a generalization of nullity patterns,
of which one example is given, is conjectured
to provide a finite determination of all bounded ratios.
\end{abstract}

\maketitle

\section{Introduction}
For an $n$-by-$n$ matrix $A=(a_{ij})$ and an index set $S\subs N \equiv
\set{1,2,\ldots,n}$, $A[S]$ is the principal submatrix of $A$ lying in the rows
and columns indicated by $S$.
Given a collection $\alpha: \alpha_1, \alpha_2, \ldots, \alpha_p \subs N$ of index
sets and exponents $\expon_1, \ldots, \expon_p \in \RR^+$, let
\[ \alpha(A) = \prod_{i=1}^p (\det A[\alpha_i])^{\expon_i}. \]
At times we also abbreviate $\alpha(A)$ as
$\alpha_1^{\expon_1}\cdots\alpha_p^{\expon_p}$,
omitting any exponents equal to $1$.
We are interested in understanding which ratios
\[
\frac{\alpha}{\beta} = \frac{\alpha(A)}{\beta(A)}
\]
have an upper bound that is independent of $A$,
provided that $A$ is positive definite (PD).
We call such ratios {\em bounded}, and
{\em absolutely bounded} if $1$ is an upper bound.
The Hadamard-Fischer inequality \cite{hj} provides
a classical family of absolutely bounded ratios
in which
$\alpha_1 = S \cup T$ and $\alpha_2 = S \cap T$,
while $\beta_1 = S$ and $\beta_2 = T$, for any two
index sets $S,T \subs N$, with all exponents $1$.
This classical family is in fact bounded over
any class of invertible matrices with positive
principal minors and weakly sign-symmetric
non-principal minors \cite{c}, and we
will call such ratios \Kot\ ratios \cite{k}.
Historical information on determinantal inequalities for
PD matrices may be found in (\cite{hj}, ch. 7).
Over real symmetric matrices, bounded ratios
are equivalent to multiplicative inequalities
on the face volumes of a parallelotope.

A ratio is determined, up to equivalence, by the
overall exponent (numerator minus denominator) of
each nonempty subset of $N.$
The exponent of the empty set is chosen
to make the sum of exponents $0$,
and the collection of $2^n$ exponents is called
the {\em formal logarithm} of $\frac{\alpha}{\beta}$,
written $\log (\frac{\alpha}{\beta})$.
Formal logarithms span a hyperplane in $\RRR$
orthogonal to the all-$1$'s vector $\allones$.

Let $\cB_n$ be the set of bounded ratios,
$\cA_n$ the set of absolutely bounded ratios,
and $\cK_n$ the set of products of positive powers of \Kot\ ratios.
Then, for all $n$, $\cK_n \subs \cA_n \subs \cB_n$.
These are multiplicative semigroups,
and there are corresponding cones
$\log (\cK_n) \subs \log(\cA_n) \subs \log (\cB_n)$.
All previously known multiplicative determinantal inequalities lie in $\cK_n$.
In \cite{jb}, necessary conditions for boundedness
were given, implicitly defining a semigroup $\cE_n$
with $\cB_n \subs \cE_n$, and it was shown that
$\cK_3 = \cE_3$ but $\cA_4 \ne \cE_4$.
Here, we define a new semigroup $\cD_n$ by imposing
linear inequalities on $\log (\cD_n)$ coming from
rank deficient positive semidefinite (PSD) matrices.
We show that $\cB_n \subs \cD_n \subs \cE_n$
for all~$n$.
We also show that $\cA_4 \ne \cB_4 = \cD_4 \ne \cE_4$,
and give explicit generators for $\cB_4$.
Going further, we show that $\cB_5 \ne \cD_5$, but we conjecture
that for each $n$ there exists some finite system
of linear inequalities,
generalizing those coming from rank deficient PSD matrices,
that is sufficient to characterize $\log (\cB_n)$.

\section{Cone theoretic determination of $\cD_n$}
We call a ratio $\frac{\alpha}{\beta}$ {\em homogeneous} if
$\alpha(D)/\beta(D) = 1$ for every PD diagonal matrix $D$,
and call the set of all such ratios $\cH_n$.
All bounded ratios are homogeneous \cite{jb},
and $\log(\cH_n)$ is the subspace of $\RRR$ that is
orthogonal to the following set of $n + 1$ vectors:
the all-$1$'s vector $\allones$ and, for each
$i \in N$, the
vector whose entry $T$ (as $T$ ranges over $T \subs N$)
is $1$ whenever $i \in T$, and $0$ otherwise.
A homogeneous ratio is uniquely determined by
the exponents of subsets with cardinality
at least $2$.
Since the dimension of $\log(\cK_n)$ is
$2^n - n - 1$, the cone $\log (\cB_n)$ has full dimension
within the subspace $\log(\cH_n)$.

Let $M$ be a matrix with $n$ columns.
We define $\nt(M) \in \RRR$, the
{\em nullity type} of $M$,
as the vector of null space dimensions
for subsets of the columns of $M$.
(By convention the empty set of columns has
nullity $0$.)
The nullity type of $M$ also gives
the multiplicity of $0$ as
an eigenvalue for any principal
submatrix of $M^*M$.
For any $n$ there exist finitely
many distinct nullity types
(corresponding to representations of labeled matroids on $n$ elements).

Our first result is that the inner product of the formal logarithm
of a ratio with any nullity type gives a necessary condition
for boundedness.

\begin{thm}\label{thm:nec}
Let $\alphabet$ be a homogeneous ratio, let $M$
be a matrix with $n$
columns,
and define a family of matrices $A_\eps$, $0 < \eps < 1$,
by
\[
  A_\eps = M^*M + \eps I.
\]
Then $\alphabet$ is bounded over the family $A_\eps$
if and only if
$\log(\alphabet)^T \nt(M) \ge 0$.
\end{thm}
\begin{proof}
Let $s=\log(\alphabet)^T \nt(M)$,
and let $r$ represent the sum of the
exponents in $\alpha$,
which is also the sum of the exponents in $\beta$.
Let $\Lambda$ be the set of all nonzero eigenvalues of $M^*M$ and
its principal submatrices,
and let $\lmin$ and $\lmax$ denote
respectively the minimum and maximum elements
of $\Lambda \cup \{1\}$,
so that $\lmin \le 1 \le \lmax$.
For any $0<\eps<1$, the matrix $A_\eps$ is PD,
and the quantity $\alphabet(A_\eps)$ can be expressed
entirely in terms of the eigenvalues of principal submatrices of $A_\eps$.
Each of these eigenvalues is $\eps$ or lies
within the range $\lmin+\eps$ to $\lmax+\eps$.
The total exponent of $\eps$ in the eigenvalue product
is exactly the inner product
$\log(\alphabet)^T \nt(M)=s$.
The contribution of all remaining eigenvalues
either to the numerator $\alpha(A_\eps)$
or to the denominator $\beta(A_\eps)$
lies within the range $\lmin^{nr}$
to $(\lmax+1)^{nr}$.
Thus we have
\[
\eps^s\left(\frac{\lmin}{\lmax+1}\right)^{nr}
\le
\alphabet(A_\eps)
\le
\eps^s\left(\frac{\lmax+1}{\lmin}\right)^{nr}.
\]
If $s < 0$ the left inequality implies that
$\alphabet(A_\eps)$ is unbounded,
and if $ s \ge 0$ the right inequality
implies that $\alphabet(A_\eps)$ is bounded by a constant.
\end{proof}

Given $n$, let
$\nu_1, \ldots, \nu_{\ell}$ be a complete list
of the nullity types of matrices
with $n$ columns.
The {\em dual nullity} semigroup $\cD_n$ is defined as the
set of homogeneous ratios $\alphabet$
such that $\log(\alphabet)^T \nu_i\ge 0$
for all $1 \le i \le \ell$.

\begin{cor}
  For all $n$, $\cB_n \subs \cD_n$.  Moreover, if each extreme ray
  of $\log(\cD_n)$ represents a bounded ratio,
  then $\cB_n = \cD_n$.
\end{cor}

The dual nullity cone $\log(\cD_n)$ is a finite intersection
of half-spaces
and thus its set of extreme rays can
(in principle, and sometimes in practice)
be explicitly calculated.
Some nullity types are redundant to this calculation:
$\nt(I)$ is trivial;
$\nt([ M_1 | \mathbf 0])
 -
 \nt(M_1 \oplus I)$
is orthogonal to $\cH_n$,
so one of these may be omitted;
and $\nt(M_1 \oplus M_2)
= \nt(M_1 \oplus I) + \nt(I \oplus M_2)$.
Given a matrix $M$ with $n$ columns,
let $\rt(M)$ be the vector in $\RRR$
whose entry for each $T \subs N$
is the rank of the subset $T$ of the
columns of $M$.
Since $\nt(M) + \rt(M)$
is the vector $\left[|T|\right]$ of cardinalities, which
is orthogonal to $\cH_n$,
$\nt(M)$ and $-\rt(M)$ are interchangeable
for the purposes of calculating $\cD_n$.
This fact can be useful computationally
when $M$ has low rank.

\begin{exam}
\label{ex1}
Let $n=3$, and let $\nu_1, \ldots, \nu_5$ be the
nullity types of the matrices
\[
  \left[
    \begin{array}{ccc}
      1 & 1 & 1
    \end{array}
  \right],
  \left[
    \begin{array}{ccc}
      0 & 1 & 1
    \end{array}
  \right],
  \left[
    \begin{array}{ccc}
      1 & 0 & 1
    \end{array}
  \right],
  \left[
    \begin{array}{ccc}
      1 & 1 & 0
    \end{array}
  \right],
  \mbox{ and }
  \left[
    \begin{array}{ccc}
      1 & 0 & 1 \\
      0 & 1 & 1
    \end{array}
  \right].
\]
Let $\cE_3$ be the intersection of the five sets
$ \{\alphabet \in \cH_3 :\ \log(\alphabet)^T \nu_i \ge 0\}.$
The six extreme rays of $\log(\cE_3)$ are the formal logarithms of
the \Kot\ ratios
\[
  \frac{\{12\}\,\emptyset\ }{\{1\}\{2\}},
  \frac{\{13\}\,\emptyset\ }{\{1\}\{3\}},
  \frac{\{23\}\,\emptyset\ }{\{2\}\{3\}},
  \frac{\{123\}\{1\}}{\{12\}\{13\}},
  \frac{\{123\}\{2\}}{\{12\}\{23\}},
  \mbox{ and }
  \frac{\{123\}\{3\}}{\{13\}\{23\}}.
\]
We thus have $\cK_3 \subs \cA_3 \subs \cB_3 \subs \cD_3 \subs \cE_3 \subs \cK_3$
and in particular $\cB_3 = \cK_3$, as was shown in \cite{jb}.
\end{exam}

The symmetric group on $n$ elements
acts naturally on $\RRR$ and
preserves
every set we have defined.
Set complementation $S^c = N \setminus S$
also acts naturally and preserves $\log(\cK_n)$ and $\log(\cH_n)$.
Since
$\frac{S}{\emptyset}(A) = \frac{S^c}{N}(A^{-1})$
by Jacobi's identity \cite{hj},
$\log(\cA_n)$ and $\log(\cB_n)$ are also invariant under
the action of complementation.
To show that $\log(\cD_n)$ is invariant
under complementation requires
some matroid theory~\cite{oxley}:
the complement of a nullity type is
equivalent, up to vectors orthogonal
to $\log(\cH_n)$,
to the nullity type of the dual matroid.

Theorem~\ref{thm:nec} generalizes
the known set-theoretic necessary conditions ST0, ST1, and ST2.
\begin{thm}
\cite{jb} For any bounded ratio $\alphabet$ and any given
index set $S \subs N$, the sum of exponents in $\alphabet$ for
supersets of $S$ is nonnegative (ST1), and likewise for subsets of $S$ (ST2).
Any ratio satisfying ST1 and ST2
also satisfies homogeneity (ST0).
\end{thm}
We define $\cE_n$ as the set of ratios satisfying
the elementary necessary conditions
ST1 and ST2 for every $S \subs N$.
These conditions can be restated in terms of nullity types.
Given an index set $S \subs N$ with
$|S| \ge 3$, define
$M_{S}$ to be the matrix of size $(n-1) \times n$
that is a permutation of $[I | e] \oplus I$,
with the $[I | e]$ summand occurring in the
columns of $S$ and the $I$ summand occurring
in the complement of $S$.
Then for $T \subs N$,
entry $T$ of $\nt(M_{S})$ is $1$
if $S \subs T$ and $0$ otherwise.
Given an index set $S \subs N$ with
$|S| \le n-2$, define
$M^{S}$ to be the matrix of size $1 \times n$
whose entries are $0$ in the columns
of $S$ and $1$ elsewhere.
Then for $T \subs N$,
entry $T$ of $\rt(M^S)$ is $0$
if $T \subs S$ and $1$ otherwise.
For example, with $n=3$, the five matrices listed in Example~\ref{ex1}
are $M^{\emptyset}$,
$M^{\{1\}}$,
$M^{\{2\}}$,
$M^{\{3\}}$,
and $M_{\{123\}}$.
\begin{prop}
\label{prop:one}
A homogeneous ratio $\alphabet$ satisfies
conditions ST1 and ST2 if and only if
$\log(\alphabet)^T \!\nt(M_S) \ge 0$
for $|S| \ge 3$ and
$\log(\alphabet)^T \!\nt(M^S) \ge 0$
for $|S| \le n-2$.
\end{prop}
\begin{proof}
The cases $|S| \le 1$ for ST1 and
$|S| \ge n-1$ for ST2 are equivalent
to the assumed homogeneity.
The case ST1 with $|S|=2$ will follow
from ST2 with $|S| = n-2$:
for a homogeneous ratio,
ST1 is satisfied for $\{i,j\}$ if and only if
ST2 is satisfied for $\{i,j\}^c$,
as can be seen
by partitioning $2^N$ into four groups
depending on the membership of $i$
and $j$, and comparing
the total exponents of these groups under homogeneity.
For $|S| \ge 3$,
$\log(\alphabet)^T \nt(M_S)$
is nonnegative if and only if
$S$ occurs as a subset
in $\alpha$ with a total exponent
at least as great as in $\beta$.
For $|S| \le n-2$,
$\log(\alphabet)^T \left(\allones - \rt(M^S)\right)$
is nonnegative if and only if
$S$ occurs as a superset
in $\alpha$ with a total exponent
at least as great as in $\beta$.
Since $\alphabet$ is homogeneous
and $\nt(M^S) + \rt(M^S) - \allones$
is orthogonal to $\log(\cH_n)$,
this is equivalent to
$\log(\alphabet)^T \nt(M^S) \ge 0$.
\end{proof}

\begin{cor}
For all $n$, $\cD_n \subs \cE_n$.
\end{cor}

The name $\cE_3$ in Example~\ref{ex1} is
now justified, and we have shown,
as in~\cite{jb}, that $\cK_3 = \cE_3$.
Since the vectors $\nt(M^S)$ for $|S| \le n-2$
and the vectors orthogonal
to $\log(\cH_3)$ together span $\RRR$,
$\log(\cB_n)$ is a pointed cone:
no nontrivial ratio is both
bounded and bounded away from $0$.

\section{Bounding ratios not in $\cK_n$}
Given a ratio $\alphabet$
in $\cD_n \setminus \cK_n$,
it may be difficult to determine whether
$\alphabet$ is bounded.
We introduce a technique that can sometimes prove boundedness, starting
with a known observation
whose first nontrivial case is $n = 3$:

\begin{lem}
\label{lem:Fied}
\cite{fiedler}
Let $A=(a_{ij})$ be an $n$-by-$n$ PD matrix with inverse
$B=(b_{ij})$.  Then
for each $i=1,\ldots,n$
\begin{equation}\label{Fied}
2\sqrt{a_{ii}b_{ii}}+(n-2)\leq\sum_{j=1}^n\sqrt{a_{jj}b_{jj}}.
\end{equation}
\end{lem}

Eliminating a copy of $i$ on each side,
replacing the sum with $(n-1)$ times the maximum, and using the fact that
$b_{ii} = \frac{\{i\}^c}{N}(A)$, we conclude:

\begin{cor}\label{cor:Fied}
For $n \ge 3$ and $A$ PD, and for any $i \in N$,
\[ \min_{j \ne i}\set{\frac{\set{i}\set{i}^c}{\{j\}\{j\}^c}(A)} \leq (n-1)^2. \]
\end{cor}

\begin{exam}
\label{ex2}
In~\cite{jb} it is shown that $\cA_4 \ne \cE_4$ using a permutation of
\[
  R_1
  =\frac{\set{124}\set{134}\set{23}\set{1}\set{4}}
          {\set{12}\set{13}\set{14}\set{24}\set{34}}. \]
Observe that this ratio is
unchanged when indices $2$ and $3$ are interchanged;
we may thus assume without loss of generality that
$\frac{\set{1}\set{23}}{\set{2}\set{13}}(A) \le \frac{\set{1}\set{23}}{\set{3}\set{12}}(A)$.
By applying Corollary~\ref{cor:Fied}
to $A[\set{123}]$ with $i=1$ we then obtain,
factoring out a pair of \Kot\ ratios,
\[
  R_1 =
    \frac{\set{124}\set{2}}{\set{12}\set{24}} \cdot
    \frac{\set{134}\set{4}}{\set{14}\set{34}} \cdot
    \frac{\set{1}\set{23}}{\set{2}\set{13}}
  \le 4,
\]
which shows that $R_1$ belongs to $\cB_4$.
\end{exam}

\section{The extreme rays of $\log(\cB_4)$}
Let $\mu_1, \ldots, \mu_{23}$ represent the distinct nullity types
of column permutations of the following seven matrices:
$M^{\emptyset}$, $M^{\{1\}}$,
$M^{\{12\}}$,
$M_{\{123\}}$,
$M_{\{1234\}}$,
\[
  M_6 =
  \left[
    \begin{array}{cccc}
    1 & 0 & 1 & 1 \\
    0 & 1 & 1 & 1
    \end{array}
  \right],
\mbox{ and }
  M_7 =
  \left[
    \begin{array}{cccc}
     1 & 1 & 1 & 1 \\
     0 & 1 & 2 & 3
    \end{array}
  \right].
\]

The intersection of $\cH_4$ with the $23$ half-spaces
$ \{x \in \RR^{16} :\ x^T\mu_i \ge 0\}$
contains $\cD_4$ and thus $\cB_4$.
There are various software packages available for computing
the extreme rays of an intersection of half-spaces in exact
arithmetic; in this case the calculation was done with
custom-written software, whose results were later verified
with the program {\tt lrs} \cite{lrs}
(available at \url{http://cgm.cs.mcgill.ca/~avis/C/lrs.html}).
The $46$ extreme rays
include the $24$ extreme rays of $\log(\cK_4)$
(those with $|S| = |T| = |S \cap T| + 1$) and
the $6$ permutations
of $\log(R_1)$ from Example~\ref{ex2}.
The ratios corresponding to the remaining $16$ extreme rays are
permutations of
\begin{equation}\label{r2}
R_2 =
\frac
   {\set{1234}\set{1234}\set{23}\set{24}\set{34}
    \set{1}\,\emptyset\ }
   {\set{123}\set{124}\set{134}\set{234}
    \set{2}\set{3}\set{4}},
\end{equation}
\begin{equation}\label{r3}
R_3 =
\frac
   {\set{1234}\set{23}\set{24}\set{34}
    \set{1}\set{1}\,\emptyset\ }
   {\set{123}\set{12}\set{13}\set{14}
    \set{2}\set{3}\set{4}},
\end{equation}
and their complements.  Since $R_2$ and $R_3$
are both symmetric in indices $2$ and $3$,
we may make the same assumption as in
Example~\ref{ex2} and conclude
from Corollary~\ref{cor:Fied} that
\[
      R_2 =
         \frac{\set{1234}\set{24}} {\set{124}\set{234}} \cdot
         \frac{\set{1234}\set{13}} {\set{123}\set{134}} \cdot
         \frac{\set{34}\,\emptyset\ } {\set{3}\set{4}} \cdot
            \frac{\set{1}\set{23}}{\set{2}\set{13}} \le 4
\]
and
\[
    R_3 =
         \frac{\set{1234}\set{24}} {\set{124}\set{234}}\cdot
         \frac{\set{124}\set{1}} {\set{12}\set{14}}\cdot
         \frac{\set{34}\,\emptyset\ } {\set{3}\set{4}}\cdot
         \frac{\set{1}\set{23}}{\set{2}\set{13}} \le 4.
\]
Although the proven bound is $4$,
experimental evidence suggests that the ratios $R_2$ and $R_3$
are absolutely bounded,
which would imply $\cK_4 \ne \cA_4$,
and that the correct upper bound for $R_1$ is $\frac{27}{16}$,
which value it is known to approach~\cite{hm}.
This is the first known case
showing $\cA_n \ne \cB_n$ for any $n$.
It has been shown \cite{fhj} that
bounded ratios
on M-matrices or inverse M-matrices
are absolutely bounded, and
preliminary work shows the
same for (invertible) totally nonnegative matrices as far as $n<6$.

The listed nullity types are thus sufficient to
define $\cD_4$, and indeed $\cB_4$.

\begin{thm}
The semigroup $\cB_4$
is generated, up to permutation and complementation,
by positive powers of $\frac{\set{12}\,\emptyset\ }{\set{1}\set{2}}$,
$\frac{\set{123}\set{1}}{\set{12}\set{13}}$, $R_1$,
$R_2$, and $R_3$.
\end{thm}
\begin{thm}
The sets $\cB_4$ and $\cD_4$ are equal: a ratio $\alphabet \in \cH_4$
is bounded if and only if
$\log(\alphabet)^T\mu_i \ge 0$
for all $i = 1, \ldots, 23$, with $\mu_i$ as listed above.
\end{thm}

We end the section with an example showing that $\cD_4 \ne \cE_4$.
The ratio
\[
\alphabet=
\frac{\set{1234}\set{134}\set{12}\set{14}\set{23}\set{24}\set{3}\,\emptyset\ }
{\set{123}\set{124}\set{234}\set{13}\set{34}\set{1}\set{2}\set{4}}
\]
satisfies ST1 and ST2 with respect to every $S \subs \{1,2,3,4\}$.
However, the inner product $\log(\alphabet)^T \nt(M_6)$ gives $-1$, and
$\alphabet$ is not bounded.

\section{The case $n = 5$}
A ratio in the semigroup $\cD_n$ is bounded
near $\eps = 0$ for any
matrix family of the form
$\left(B+\eps C\right)^*\left(B+\eps C\right)$,
where $B$ is singular
and $C$ is generic in the sense that
$C x = B y$ and $B x =  0$
imply $ x =  0$.
We have shown that for $n=4$ such matrix families,
whose behavior depends only on the nullity type of $B$,
are sufficient to determine $\cB_4$.
The following example shows that for $n \ge 5$,
more general
matrix families must be considered.
\begin{exam}
\label{ex3}
Let $n=5$ and consider the ratio
\[
  Q =
  \frac{\set{12345}\set{1345}\set{2345}\set{123}\set{125}\set{34}\set{45}\set{1}\set{2}\,\emptyset\ }
  {\set{1234}\set{1235}\set{145}\set{245}\set{345}\set{12}\set{13}\set{23}\set{4}\set{5}}.
\]
We claim that $Q \in \cD_5$.
Since $Q$ is self-complementary, it is only necessary to
check against matrices of rank up to $\lfloor \frac52 \rfloor$,
i.e.\ $M$ of size $2 \times 5$.
Uniformly deleting a specified index element in the sets of $Q$ yields a product
of \Kot\ ratios in all five cases, which eliminates the
case in which $M$ has a zero column (using homogeneity).
The nullity type of $M$ now depends only on a partition
of the columns $\{1,2,3,4,5\}$ into parallel classes.
Partitions into exactly two blocks give the nullity
type of a direct sum and are thus redundant,
leaving $37$ cases to check.

Now let
\[
  P =
  \left[
    \begin{array}{ccccc}
      1  & 1  & 1  & 1  & 1   \\
      0  &\eps& 0  & 1  & 2   \\
      0  & 0  &\eps& 1  & 2   \\
      0  & 0  & 0  &\eps& 0   \\
      0  & 0  & 0  & 0  &\eps \\
    \end{array}
  \right],
\]
define $A_\eps$ as $P^*P$,
and consider the polynomial $\det A_\eps[ S ]$ for some $S \subs N$.
This is a nonnegative function of $\eps$, and so for every $S$
the dominating term for $\eps$ small must
be an even power $C_S\eps^{2d_S}$ for $C_S > 0$ and $d_S$ a nonnegative integer.
Call the vector $\left[d_S\right] \in \RRR$
the {\em asymptotic nullity type} of $P$,
or $\asn(P)$.
The fact that $\log(Q)^T \asn(P) = -1$
means that the ratio $Q$ is not bounded, and $\cB_5 \ne \cD_5$.
\end{exam}

We expect that any one-parameter matrix
family making a particular ratio unbounded
can be adequately approximated by
polynomials in $\eps$,
and further that the maximum necessary degree of
the approximation depends only on $n$.
We thus expect $\log(B_n)$ to be
a polyhedral cone for all $n$,
as it is for $n \le 4$.

\begin{conj}
Given any $n$,
define the asymptotic nullity type $\asn(P)$ of an
invertible $n \times n$ matrix $P$ of polynomials
in $\eps$
  as in Example~\ref{ex3}.
Then there exists a finite list of polynomial matrices
$P_1$, \ldots, $P_\ell$
such that a homogeneous ratio $\alphabet$
is bounded
if and only if
$\log(\alphabet)^T \asn(P_i) \ge 0$
for all $1 \le i \le \ell$.
\end{conj}

\bibliographystyle{amsplain}
\bibliography{hj4}

\end{document}

config: arxiv


TITLE: Name of result implying $\sum\limits_{n=1}^{\infty}n^2\exp(-n^2)<\int_{1}^{\infty}\nu^2\exp(-\nu^2)d\nu$
QUESTION [0 upvotes]: I need to use the following inequality:
$$\sum_{n=1}^{\infty}n^2\exp(-n^2)<\int_{1}^{\infty}\nu^2\exp(-\nu^2)d\nu\tag{1}$$
What would be the name of a theorem yielding this inequality?

REPLY [5 votes]: Not a theorem, simply the fact that the function $x\mapsto x^2\mathrm e^{-x^2}$ is decreasing on $x\geqslant1$ hence, for every $n\geqslant1$, $$u(n)\geqslant\int_n^{n+1}u(x)\mathrm dx,$$ and, summing these, $$\sum_{n=1}^\infty u(n)\geqslant\int_1^\infty u(x)\mathrm dx.$$ Thus the upper bound in your post is wrong. To get an upper bound, note that the same argument yields $$\sum_{n=1}^\infty u(n)\leqslant\int_0^\infty u(x)\mathrm dx=\sqrt\pi.$$


TITLE: Doubt with partial pressures
QUESTION [0 upvotes]: I have a conceptual doubt about partial pressures. Suppose you have a closed system composed of a gas mixture, say Argon and Helium. If they behave according to Ideal Gas Law, then the molar fraction of each species should be equal to the partial pressure of the species over the total pressure (yi=Pi/P).
Therefore, if the mixture has a molar composition of, say 20% Ar and 80% He, then the partial pressure of Argon should be 0.2P and for Helium it should be 0.8P. However, does this pressure needs to be manometric or absolute pressure?, as I said in the beginning, the system is closed but due to atmospheric pressure, the absolute pressure of the He-Ar mixture should be more than the atmospheric pressure (say 1 atm for simplicity and 0.5 atm for manometric pressure). If the P involved in the calculations must be absolute, then that means that the partial pressure of Ar and He should be 0.2(1.5) atm and 0.8(1.5) atm, respectively.
My confusion comes from Dalton's Law, which says that the total pressure exerted is the sum of the partial pressures of all the gases. But if we say that the total pressure is 1.5 atm, we are taking into account the atmospheric pressure there as if that pressure is being caused by Helium and Argon, but that shouldn't be true. I am not sure if Pascal's Law is the answer to this question, if so, let me know please.
Another huge confusion (and question) that I have is the following. In several books that talk about gas mixtures (for example binary mixtures in mass transfer books), they talk about composition of the gases in the mixture as in my previous He-Ar example. For example, from a problem in one of those books, they provide the composition of the mixture, say 50% CO and 50% Ni(CO)4 (the species involved are not really important, the important thing is that it is a gas mixture), and they also state that the pressure is 1 atm. My confusion here is the following.
If they talk about compositions of the gaseous mixtures, then that must mean (in my opinion) that they are talking about a closed system. Else, the system would be open to the atmosphere, and the gases in the system would dilute in air, where the mixture (air-CO-Ni(CO)4) would have a molar composition of practically a 100% for air. I think that this argument is valid to prove that the system in question must be closed. But, if the system is closed, how can the pressure be 1 atm?, if the P that I was talking about in the first question is indeed the absolute pressure, then the atmospheric pressure should add to the manometric pressure, and therefore, the pressure should be greater than 1 atm necessarily (unless the volume of the closed system containing CO and Ni(CO)4 is so big that the manometric pressure is practically negligible, of course). Does it make sense to talk about gaseous mixtures with definite compositions with a pressure of 1 atm?, how accurate is this assumption?
If my questions are not clear enough, please let me know in order to rephrase. I would really like to get these misconceptions solved. Thanks in advance!

REPLY [2 votes]: You are mistaking manometric pressure for gauge pressure and systems with an impermeable but deformable barrier for closed systems.
Manometric pressure is what a manometer measures - which depends on how the manometer is calibrated. A manometer with one end containing a captive gas can be calibrated for gauge pressure (pressure above 1 atmosphere) or absolute pressure (pressure above 0). It's simply a matter of what numbers you draw on the dial. It could alternatively be left open on both ends and measure true differential pressure.
Gauge pressure is relative pressure, either against a standard calibration reference (typically 1 atmosphere) or using a differential pressure sensor (for example, a U-shape manometer with one end open to atmosphere and the other end open to the system to be measured). If a tire is filled with 20% Ar and 80% He to a gauge pressure of 400 kPa calibrated for an atmospheric pressure of 100kPa, the absolute pressure in the tire is 500 kPa and the partial pressures of Ar and He are 100 kPa and 400 kPa respectively.

A system with an impermeable but deformable barrier can be at 1 atmosphere, corresponding to a gauge pressure of 0. It cannot fall below exterior pressure as long as the barrier can still be deformed to reduce the volume inside the container.
A closed system is one with an impermeable, insulated, and rigid barrier, that is, one for which work across the barrier is exactly zero everywhere. The absolute pressure inside such a chamber can have any value greater than 0.
As a general rule:

If the system has a deformable barrier, like a piston, tire, or
balloon, or is designed to add pressure (a pump), pressure probably means
gauge pressure with a reference of 1 atmosphere.

If the system has a rigid barrier or no constraints except the pull
of gravity, such as a vacuum chamber, a bomb, the weather at a
certain altitude, a certain depth in a body of water, the pressure in a deep space nebula, or a textbook
problem declaring a "closed system", pressure probably means absolute pressure.


TITLE: $P$ is positive definite and $A=PA^*P^{-1}$ $\mathop \Rightarrow \limits^? \sigma (A) \subset \mathbb{R}$
QUESTION [1 upvotes]: Let $A,P\in {M_n}$, and $P$ is positive definite and $A=PA^*P^{-1}$.
Is this true that, all eigenvalue of $A$ is real?

REPLY [1 votes]: I assume that $P$ is invertible.
Note that $PA^* = AP$.  Because $P$ is Hermitian, we have
$$
(AP)^* = AP
$$
so that $AP$ is Hermitian.

From there, apply the steps in the comment below: $AP$ is Hermitian, so $P^{-1/2}AP^{1/2}$ is Hermitian, so $A$ is similar to a Hermitian matrix.


TITLE: Derivatives Affecting the Shape of a Graph
QUESTION [0 upvotes]: $f(x)= x^4 - 50x^2 + 4$
Okay, so I get that my first step is to find the Critical Points.
Here is what I have for that:
$f'(x)= 4x(x - 5)(x + 5)=0$
,so my Critical Points are -5,0,5.
I am having trouble with the interval chart. I may need someone to really dumb this down for me as I'm probably over analyzing this. I'm searching for where it increases at, decreases at, the absolute min and max, the inflection point, and where the concave up and down takes place.
Any help would be much appreciated.

REPLY [0 votes]: Find derivative of function first, and check the critical points.
$\frac{\mathrm{d}}{\mathrm{d}x}(x^4-50 x^2+4) = 4x(x^2-25)=4x(x-5)(x+5)$
The critical points are $x=-5,0,5$, and $f(-5) = -621$, $f(0) = 4$, $f(5) = -621$.
$f$ is decreasing on $(-\infty , -5)$; $f$ is increasing on $(-5,0)$; $f$ is decreasing on $(0,5)$; $f$ is increasing on $(5,+\infty)$.
$f^{\prime\prime} (x) = (4x^3-100x)^\prime = 12x^2-100 = 12 ( x - \sqrt{\frac{25}{3}}) ( x + \sqrt{\frac{25}{3}})$. The inflection points are when $f^{\prime\prime}$ changes its sign. They are at $x = \frac{5\sqrt{3}}{3}$ and $x = -\frac{5\sqrt{3}}{3}$.


TITLE: Integration of $\int_0^1 x\log\frac{1+x}{1-x} \, dx$
QUESTION [1 upvotes]: Wolfram Alpha gives
$$\int_0^1 x\log \frac{1+x}{1-x}\,dx=1$$
I tried integration by part. But there is a convergence issue at $x=1$. Any help?

REPLY [0 votes]: We want to find $\int_0^1 x\log(1+x)\,dx-\int_0^1 x\ln(1-x)\,dx$.
Since the second integral is under suspicion, let us look at it.  Let $u=\ln(1-x)$ and $dv=x\,dx$. Then we have $du=-\frac{1}{1-x}\,dx$, and we can take $v=\frac{x^2}{2}-\frac{1}{2}$. (We used a little trick here!)
So our antiderivative is
$$\ln(1-x)\left(\frac{x^2}{2}-\frac{1}{2}\right) -\int \frac{1+x}{2}\,dx$$
Note that $\lim_{x\to 1^-}(1-x)\ln(1-x)=0$. It follows that
$$\int_0^1 x\ln(1-x)\,dx=-\int_0^1 \frac{1+x}{2}\,dx=-\frac{3}{4}.$$
The other integral is done the same way, except there is no convergence issue to worry about.


TITLE: Fitch System proof for $(\neg p \implies q) \implies ((\neg p \implies \neg q) \implies p)$ with no premises.
QUESTION [2 upvotes]: How to solve this problem using a Fitch System proof for $( \neg p \implies q) \implies ((\neg p \implies \neg q) \implies p)$ with no premises?
I tried assuming $( \neg p \implies q) $ then assuming $ \neg p $ but where do I go from there to get to $((\neg p \implies \neg q) \implies p)$?

REPLY [2 votes]: I wasn't sure how to type out the Fitch layout in any other way so sorry about the typesetting. I spent a long time trying to write a proof that didn't use negation elimination but I couldn't think of one. This works though, it's just not ideal.
|$\neg p \rightarrow q\qquad (\mathrm{assumption})$
| |$\neg p \rightarrow \neg q\qquad (\mathrm{assumption,\ want}\ \neg\neg p)$
| |$\neg \neg p\qquad (\mathrm{negation\ introduction}, 1,2)$
| |$p\qquad (\mathrm{negation\ elimination}, 3)$
|$(\neg p \rightarrow \neg q)\rightarrow p \qquad(\mathrm{implication\ introduction}, 2,4)$
$(\neg p \rightarrow q) \rightarrow ((\neg p \rightarrow \neg q)\rightarrow p) \qquad(\mathrm{implication\ introduction}, 1,5)$


TITLE: What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka)
QUESTION [29 upvotes]: Kronheimer and Mrowka showed that the Khovanov homology detects the unknot.
Bar-Natan showed a program to compute the Khovanov homology fast: there was no rigorous complexity analysis of the algorithm, but it is estimated by Bar-Natan that the algorithm runs in time proportional to the square root of the number of crossings, so it is even less than linear in the number of crossings.

What I might understand from this, is that if we have:

a proof for the correctness of Bar-Natan's algorithm
a rigorous algorithm analysis showing the run time of the algorithm is polynomial or less

then we have a proof that the unknotting problem is in P.
I guess this is not really the case.
Is what I assume here true? if not, why? (maybe Bar-Natan's algorithm is not deterministic?)

REPLY [24 votes]: This isn't directly what you ask, but it's also worth noting that unknot detection is in $\text{NP} \cap \text{co-NP}$, that is, there are polynomial-checkable certificates that will show that either a knot is the unknot or that the knot is not the unknot. The $\text{NP}$ certificate uses normal surface theory:

Ian Agol, Joel Hass, William Thurston, The computational complexity of knot genus and spanning area. Trans. Amer. Math. Soc. 358 (2006), no. 9, 3821–3850.

The $\text{co-NP}$ certificate is currently conditional on the Generalized Riemann Hypothesis, and is based on finding representations of the knot group:

Greg Kuperberg, Knottedness is in NP, modulo GRH. Adv. Math. 256 (2014), 493–506.

(There ought to be another proof of the $\text{co-NP}$ result using normal surface theory and the notion of hierarchies. Ian Agol sketched that some time ago, but the details are difficult.)
The class $\text{NP} \cap \text{co-NP}$ is relatively small, and this gives reasons to believe that detecting the unknot is in $\text{P}$.
(I would have made this a comment, but I think it's too long for that.)


TITLE: Connectedness of covering space
QUESTION [3 upvotes]: Suppose we have a covering map $f:E \to B$, where $B$ is a connected and path-connected space and $E$ is a p-sheeted cover of $B$.
Are the following statements equivalent?

$E$ is a non-trivial covering, i.e. $E$ is not a disjoint union of $p$ copies of $B$.
$E$ is connected.
$E$ is path connected.
There exists a loop in $B$ whose preimage is an interval in $E$.

I think the equivlance between 1 and 4 is easy to see since a trivial covering will have the property that the preimage of any loop is a disjoint union of $p$ loops. But I don't really understand the relation between 1 and 2 or 1 and 3. Definitely when $E$ is trivial, it is neither path-connected nor connected, but what about the other way around?
Or, is there any way to see if the covering space is connected/path-connected by looking at the covering map?
Any comment/help is appreciated.

REPLY [2 votes]: 1 and not 2/3: a union of two non-trivial coverings.
2/3 and not 1: $f = \text{id}_B$.
2 and not 3: take the famous counterexample, make it path-connected:

and cover it spirally, as in the universal cover for $S^1$. Or do the same with the so-called extended long line, which is imo more fun. (Obviously, you can make p finite by modifying this way other $S^1$ coverings.)


TITLE: Combinatorics. A box contains 20 balls numbered $1,2,3,...,20$.
QUESTION [1 upvotes]: A box contains $20$ balls numbered $1,2,3,...,20$. If 3 balls are randomly taken from the box, without replacement, what is probability that one of them is the average of the other two?

Which one of these is the correct answer?

7/45
3/38
6/155
3/154

REPLY [0 votes]: Refer to the table:
$$\begin{array}{c|c|c}
\text{Middle (average) number}&\text{Sets}&\text{Number of sets}\\
\hline
2&\{1,2,3\}&1\\
3&\{1,3,5\},\{2,3,4\}&2\\
4&\{1,4,7\},\{2,4,6\},\{3,4,5\}&3\\
\vdots&\vdots&\vdots\\
9&\{1,9,17\},\{2,9,16\},\cdots,\{8,9,10\}&8\\
10&\{1,10,19\},\{2,10,18\},\cdots,\{9,10,11\}&9\\
11&\{2,11,20\},\{3,11,19\},\cdots,\{10,11,12\}&9\\
12&\{4,12,20\},\{5,12,19\},\cdots,\{11,12,13\}&8\\
\vdots&\vdots&\vdots\\
18&\{16,18,20\},\{17,18,19\}&2\\
19&\{18,19,20\}&1\\
\hline
\text{Total}&&2\cdot \frac{(1+9)\cdot 9}{2}=90
\end{array}$$
Hence, the required probability is:
$$\frac{90}{{20\choose 3}}=\frac{90\cdot 1\cdot 2\cdot 3}{20\cdot 19\cdot 18}=\frac{3}{38}.$$


TITLE: Uniqueness of the weak derivative with the fundamental lemma of the Calculus of Variations
QUESTION [1 upvotes]: I have a homework question where I need to prove why a specific integrable (but not continuous) function $u$ on the interval $[-1,1]$ has one and only one weak derivative. This raised the question of how to prove that if $f$ and $g$ are weak derivatives of an arbitrary integrable $u: [a,b] \to \mathbb{R}$, then $f = g$.
Given any $h \in C^1([a,b])$ that is zero at the endpoints, we obtain $\int_a^b [f(x)-g(x)]h(x) \, dx = 0$ from the definition of weak derivative. If $\varphi := f-g$ was continuous, then obviously we could just apply the fundamental lemma and we'd get $f=g$, but what if the finite or countable set $X \subset [a,b]$ of $\varphi$'s discontinuities is non-empty?
I've only looked at the finite case $X:=\{x_1,...,x_{n-1}\}, \, n \geq 2$, and partitioned the interval into the set of open intervals $I_{k} := (x_{k-1}, x_k), \, k=1,...,n$ (where $x_0=a$ and $x_n=b$). $\varphi h$ is continuous on all of these sub-intervals, and I'm trying to use a proof by strong induction: given $1 \leq p \leq n$, assume that $\varphi \equiv 0$ on $n-s$ of these intervals $I_k$ (for all $0 \leq s < p$) implies $\varphi \equiv 0$ on $[a,b]\setminus X$; now prove that if $\varphi \equiv 0$ on $n-p$ of the intervals, then $\varphi \equiv 0$ on $[a,b] \setminus X$. Since $X$ has measure zero, we show that $f=g$ up to a null set.
I think I can prove the case where $X$ is countable after I show it holds for the finite one.

REPLY [1 votes]: You'd want to use the fact that $\{h \in C^1([a, b]) | h(a) = h(b) = 0\}$ is a dense subset of $L^1([a, b])$.
Consider the measurable set $S_n = \{x \in [a, b] | f(x) - g(x) > \frac{1}{n}\}$. Then approximate the characteristic function $\chi_S$ within $\epsilon$ by a function $k \in C^1([a, b])$ such that $k(a) = k(b) = 0$. Then we have $\int (f - g) k\; dx = 0$. Then we have $\int (f - g) \chi_S \; dx < \epsilon$ for all positive $\epsilon$. And we also have $\int (f - g) \chi_S \; dx \geq \frac{1}{n} \mu(S_n)$, where $\mu$ is the measure. Thus, we must have $\mu(S_n) = 0$.
Therefore, we have $\mu(\{x \in [a, b] | f(x) - g(x) > 0\}) = \mu(\bigcup\limits_{n = 0}^\infty S_n) \leq \sum\limits_{n = 0}^\infty \mu(S_n) = 0$.
Similarly, we have $\mu(\{x \in [a, b] | f(x) - g(x) < 0\}) = 0$.
Thus, we see $f = g$ almost everywhere.


TITLE: Problem in valuation theory
QUESTION [2 upvotes]: Find $\alpha\in \mathbb{Q}$, such that $v_2(\alpha-1/3)\ge 2$, $v_3(\alpha-1/2)\ge 3$ and $|\alpha-1|_\infty<1/2$, where $v_p$ is the $p$-adic exponential valuation and $|\cdot|_\infty$ is the usual absolute value.
Thanks in advance!

REPLY [1 votes]: Hint: If $\alpha = \frac{a}{b}$ then
$\alpha-\frac{1}{2} = \frac{2a-b}{2b}$
$\alpha-\frac{1}{3} = \frac{3a-b}{3b}$
You need to make the first fraction divisible by a high power of 3, and the second divisible by a high power of 2. It's easiest to make $b$ relatively prime to 6 so you don't have to worry about the denominators. Pick such a $b$. Can you find an $a$ such that $2a-b$ is divisible by 27? Can you find an $a$ that makes $3a-b$ divisible by 4? Can you find an $a$ that does both? Finally, can you make $a$ close enough to $b$ so that $\frac{a}{b}$ is not too far from 1?


TITLE: Proving a lemma for a dichotomy
QUESTION [1 upvotes]: I am currently trying to prove the Rolle theorem by dichotomy. I think it is possible and I found the following property, that might be useful :

let $f : [a,b]\to \mathbf{R} $ be a continuous function with $f(a)-f(b)=0$, then there exist $\alpha$ and $\beta$ such that $a<\alpha<\beta<b$, with $\beta-\alpha\leq\frac{b-a}{2}$ and $f(\alpha)=f(\beta)$

To prove this lemma, I thought I'd use the IVT on the following function :
$$\forall x \in I=\left[a,\frac{a+b}{2}\right], g(x)=f\left(x-\frac{b-a}{2}\right)-f(x)$$
to prove that there exist $\alpha \in I$ such that $g(\alpha)=0$, and then maybe proving that there exist a $\beta$ in $\left[\frac{a+b}{2},b\right]$ such that $f(\alpha)=f(\beta)$
From there, the lemma would (?) follow,
Any Help is appreciated,
T.D

REPLY [1 votes]: $$f(x) \ge 0, f\left(\frac{a+b}{2}\right) > 0 \\ \Huge\overset{\mmlToken{mo}{⏜}}{\overline{\phantom{ABC}}\,} \\ x = a \qquad \qquad x = b$$
Without loss of generality, assume that $f(a) = f(b) = 0$.  I'll first prove the lemma for the simple case $f \ge 0$ on $[a,b]$ with $f\left(\dfrac{a+b}{2}\right) > 0$.
The auxiliary function $$g(x)=f\left(x-\frac{b-a}{2}\right)-f(x)$$ should be defined on the right-half of the interval $$I=\left[\frac{a+b}{2},b\right].$$
This enables us to see that
\begin{align}
g\left(\frac{a+b}{2}\right) &= f(a) - f\left(\frac{a+b}{2}\right) = 0 - f\left(\frac{a+b}{2}\right) < 0\text{, and} \\
g(b) &= f\left(\frac{a+b}{2}\right) - f(b) = f\left(\frac{a+b}{2}\right) - 0 > 0.
\end{align}
Therefore, there exists $\beta \in I$ such that $g(\beta) = 0$.
$$\text{i.e.} f(\alpha) - f(\beta) = 0 \text{, where } \alpha := \beta - \frac{a+b}{2}.$$
$$f\left(\frac{a+b}{2}\right) = 0 \\ \huge \overset{\mmlToken{mo}{⏜}}{\overline{\phantom{AB}}\,} \overset{\mmlToken{mo}{⏜}}{\overline{\phantom{AB}}\,} \\ x = a \qquad \qquad x = b$$
Then, prove the lemma for another special case $f\ge 0$ on $I$ with $f\left(\dfrac{a+b}{2}\right) = 0$ and that $f$ is finitely many roots on $I$.  Since the number of roots of $f$ on $I$ is finite, we can easily reduce this into the simply case: just like a subinterval $[c,d] \subseteq I$ so that $f(x) \ne 0$ for all $x \in (c,d)$.  This reduces to the first case.

Graph of $f(x) = \begin{cases}x \sin(1/x) & \text{if } x \ne 0 \\ 0 & \text{if } x = 0 \end{cases}$ (source of picture)
The remaining case is even simpler: $f$ has infinitely many crossings with the $x$-axis on interval $I$.  An argument by length should enable you to find the desired subinterval $[\alpha,\beta]$.

Edit: this answer addresses the original version of the question.
Your lemma is false.  Take $f(x) = 689x$ defined on $[0,8964]$ as a counterexample.  $f(0)f(8964) = 0 \times 8964 = 0$, but since $f$ is strictly increasing, $f$ is injective, so no distinct interior points $\alpha$ and $\beta$ in the domain can satisfy $f(\alpha) = f(\beta)$.


TITLE: Simple first-order linear differential equation
QUESTION [0 upvotes]: It's been a while since I covered DE's and somehow I can't solve the following using the general procedure that I found online:
$$ y' = \frac{4}{3}y - 4 $$
To find a particular solution, I can equate $-4$ to $P(x)=Bx+C$, which would yield $P(x)=-4$. Then, I use the general solution $y(x)=Ae^{ax}+P(x)$, which would yield me:
$$ y(x) =Ae^{ax}-4  $$
Given no initial value, I am not sure whether this would be correct.
Is it correct? If not, what did I do wrong?

REPLY [1 votes]: the general form of first order liner D.E
$$y'+P(x)y=Q(x)$$
so that $P(x)=-\frac{4}{3}$ and $Q(x)=-4$
$$\rho=e^{\int P(x)dx}=e^{-\frac{4}{3}x}$$
$$\rho.y=\int \rho Q(x)dx=\int e^{-\frac{4}{3}x}(-4)dx=3e^{-\frac{4}{3}x}+C$$
hence
$$y=3+Ce^{\frac{4}{3}x}$$


text:
\begin{document}
\title{The $e$-vector of a simplicial complex}
\author{Wayne A. Johnson\footnote{Department of Mathematical Sciences, Westminster College, Fulton, MO} \and Wiktor J. Mogilski\footnote{Department of Mathematical Sciences, Indiana University South Bend, South Bend, IN}}

\maketitle

\begin{abstract}
We study the exponential Hilbert series (both coarsely- and finely-graded) of the Stanley-Reisner ring of an abstract simplicial complex, $\Delta$, and we introduce the $e$-vector of $\Delta$, which relates to the coefficients of the exponential Hilbert series. We explore the relationship of the $e$-vector with the classical $f$-vector and $h$-vector of $\Delta$ while simultaneously investigating the geometric information that the $e$-vector encodes about $\Delta$. We then prove a simple combinatorial identity for the $e$-vector in the case where $\Delta$ is an Eulerian manifold.
\vspace{1 pc}
\\
\noindent \emph{Keywords}: simplicial complex; Hilbert series; Stanley-Reisner ring; Eulerian manifold
\end{abstract}

\section{Introduction}

We begin by reviewing some preliminary information on simplicial complexes. In each of the following subsections, we present relevant results on the objects of study in the sequel: the Stanley-Reisner ring, Hilbert series, and the Dehn-Sommerville equations. The goal of this paper is to introduce a new combinatorial invariant of an abstract simplicial complex, which we call the $e$-vector of the complex, and explore its properties. In \S1.1, we review more general properties of simplicial complexes; we focus on the combinatorial objects needed for \S2, \S3, and \S4 in \S1.2.

\subsection{Simplicial complexes and the Stanley-Reisner Ring}

Let $\Delta$ be an abstract simplicial complex. Recall (see, for example, \cite{MiS}) that the \textit{Stanley-Reisner ideal} of $\Delta$, denoted $I_\Delta$ is defined to be the ideal generated by the monomials corresponding to the non-faces of $\Delta$. Then the \textit{Stanley-Reisner ring} is defined to be the quotient ring $S/I_\Delta$, where $S=k[x_1,\dots,x_n]$ and $\{1,2,\dots,n\}$ is the vertex set of $\Delta$. Throughout the paper, $S$ will always denote this polynomial ring.

The algebraic and combinatorial properties of the Stanley-Reisner ring of a simplicial complex have been studied extensively (see \cite{MiS}, \cite{Stan96} for broad treatments). We will mostly be concerned with studying the Hilbert series of $S/I_\Delta$, or more specifically, an exponential analogue of the Hilbert series. Recall that, for any $\mathbb{N}^n$-graded $S$-module, $M$, we define the \emph{Hilbert series} of $M$ to be the formal power series
\begin{center}
$HS(M;x_1,\dots,x_n)=\displaystyle\sum_{\textbf{a}\in\mathbb{N}^n}\dim_k(M_\textbf{a})\textbf{x}^\textbf{a}$,
\end{center}
where, if $\textbf{a}=(a_1,\dots,a_n)$, we define $\textbf{x}^\textbf{a}=x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}$. Note that the formal power series $HS(M;x_1,\dots,x_n)$ is often called the \textit{fine} or \textit{finely-graded} Hilbert series of $M$. Setting each $x_i=t$, we get a formal power series in one variable, $HS(M;t)$, which is often called the \textit{coarse} or \textit{coarsely-graded} Hilbert series of $M$. If we do not specify which series we are dealing with, it can be assumed that we are discussing the \textit{finely-graded} Hilbert series.

As any ideal generated by monomials will automatically be graded, the Stanley-Reisner ring inherits an $\mathbb{N}^n$-gradation from $S$. The Hilbert series of the Stanley-Reisner ring has been extensively studied. We will be concerned with an analogue of $HS(M;x_1,\dots,x_n)$ that has been studied considerably less thoroughly. As in \cite{Joh}, define the \textit{exponential Hilbert series} of $M$ to be the formal power series
\begin{center}
$E(M;x_1,\dots,x_n)=\displaystyle\sum_{\textbf{a}\in\mathbb{N}^n}\dim_k(M_\textbf{a})\frac{\textbf{x}^\textbf{a}}{\textbf{a}!}$,
\end{center}
where $\textbf{a}!:=(a_1)!(a_2)!\dots(a_n)!$. In similar fashion to $HS(M;x_1,\dots,x_n)$, we consider the exponential series in fine and coarse flavors. If we wish to equate the variables to obtain the coarse exponential series, we denote this by $E(M;t)$. \S2 is especially concerned with the study of both $E(M;x_1,\dots,x_n)$ and $E(M;t)$ in the case $M=S/I_\Delta$.

\subsection{The $f$-vector and the $h$-vector}

An abstract simplicial complex has two classical combinatorial invariants: the $f$-vector and the $h$-vector. The $f$-\emph{vector}, also called the \textit{face vector} of $\Delta$ is usually written as $(f_{-1},f_0,\dots,f_{d-1})$, where $f_i$ give the number of $i$-faces of $\Delta$. It is incredibly common to count the empty set as the lone $-1$-face, and so for all complexes (save the \emph{void complex}, which is the unique complex which has no faces), we have $f_{-1}=1$. Then $f_0$ counts the number of vertices of $\Delta$, $f_1$ counts the number of edges of $\Delta$, and so on.

Relating to the $f$-vector is the $h$-vector, which arises when computing the course Hibert series of $S/I_\Delta$. As can be found in \cite{MiS} or \cite{Stan96}, the coarse Hilbert series of $S/I_\Delta$ has the form
\begin{center}
$HS(S/I_\Delta;t)=\displaystyle\frac{K(t)}{(1-t)^d}$,
\end{center}
where $K(t)$ is a polynomial (of degree $d$) with integer coefficients. If we write the polynomial as
\begin{center}
$K(t)=h_0+h_1t+h_2t^2+\dots+h_dt^d$,
\end{center}
then the vector $(h_0,h_1,\dots,h_d)$ consisting of the coefficients of $K(t)$ is called the $h$-\emph{vector} of $\Delta$.

The relationship between the $f$-vector and the $h$-vector was a topic of extensive study in the 1960s, 70s, and 80s, arguably culminating in the proofs of the Upper Bound Conjecture in \cite{Stan75} of Stanley, and the $g$-Theorem in \cite{Stan80} of Stanley, and \cite{BL80} and \cite{BL81} of Billera and Lee. The results of these papers and other useful results pertaining to the $f$-vector and the $h$-vector are collected in Chapter II of \cite{Stan96}. We present below those most necessary for our treatment of Eulerian complexes in \S4.

A part of the $g$-Theorem guarantees that the components of the $h$-vector satisfy $h_k=h_{d-k}$ whenever $\Delta$ is the boundary of a polytope (or more generally, an Eulerian sphere). These equations are referred to as the \emph{Dehn-Sommerville equations}. In \cite{Stan96}, it is shown that these equations relate to the intersection cohomology of a certain toric variety associated to the polytope. Thus, the $h$-vector records more data about $\Delta$ than just the formulation of the Hilbert series.

One further fact about the $h$-vector is that it determines the $f$-vector and vice versa. We exploit this relationship in \S2.2 and \S4.1. The exact relationship between the two is first presented in equation (2.6).

\section{Exponential Hilbert series and the $e$-vector}

In this section, we begin with a broader discussion of the exponential Hilbert series of certain $S$-modules. First, note that if $M=S$, we have
\begin{center}
$E(S;x_1,\dots,x_n)=e^{x_1}e^{x_2}\dots e^{x_n}=\textbf{e}^\textbf{x}$.
\end{center}
The $S$-modules we will chiefly be concerned with are those generated by a set of fixed monomials. We begin with the simple case of the free $S$-module generated by $\textbf{x}^\textbf{a}$. Following the notation in \cite{MiS}, denote such a module by $S(-\textbf{a})$. In analogy to the ordinary Hilbert series, we have the following result.
\begin{prop}
The exponential Hilbert series of $S(-\textbf{a})$ has the form
\begin{center}
$E(S(-\textbf{a});x_1,\dots,x_n)=\displaystyle\prod_{i=1}^n\left(e^{x_i}-\sum_{k=0}^{a_i-1}\frac{x^k}{k!}\right)$.
\end{center}
\end{prop}
\begin{proof}
First, note that $S(-\textbf{a})=S\cdot\textbf{x}^\textbf{a}$, and we then have
\begin{center}
$E(S(-\textbf{a});x_1,\dots,x_n)=\displaystyle\sum_{\textbf{b}\in\mathbb{N}^n}\frac{\textbf{x}^{\textbf{a}+\textbf{b}}}{(\textbf{a}+\textbf{b})!}=\textbf{x}^\textbf{a}\sum_{\textbf{b}\in\mathbb{N}^n}\frac{\textbf{x}^{\textbf{b}}}{(\textbf{a}+\textbf{b})!}$.
\end{center}
In order to compute the series on the right, we first compute the univariate version of the series. If there is only one variable, then we have
\begin{center}
$\displaystyle\sum_{k\in\mathbb{N}}\frac{x^k}{(k+d)!}=\frac{e^x-\sum_{j=0}^{d-1}\frac{x^j}{j!}}{x^d}$.
\end{center}
With that in mind, our original series becomes
\begin{center}
$E(S(-\textbf{a});x_1,\dots,x_n)=\textbf{x}^\textbf{a}\displaystyle\prod_{i=1}^n\frac{e^x-\sum_{j=0}^{a_i-1}\frac{x_i^j}{j!}}{x_i^{a_i}}$,
\end{center}
and distributing the $\textbf{x}^\textbf{a}$ yields the result.
\end{proof}
The remainder of this section is devoted to expanding this result to the Stanley-Reisner ring, $S/I_\Delta$, of a simplicial complex, $\Delta$. While the argument in this case is similar to the above, the structure of $I_\Delta$ greatly simplifies the formula of the exponential Hilbert series, as the monomials are square-free.

\subsection{The multivariate case}

As in \S1, let $\Delta$ be an abstract simplicial complex with Stanley-Reisner ideal $I_\Delta$. In this subsection, we compute the fine exponential Hilbert series of $S/I_\Delta$. The next subsection is devoted to the study of the coarse exponential Hilbert series. The main result of this subsection is below.

\begin{thm}
Let $\Delta$ be an abstract simplicial complex with Stanley-Reisner ideal $I_\Delta$. Then
\begin{center}
$E(S/I_\Delta;x_1,\dots,x_n)=\displaystyle\sum_{\sigma\in\Delta}\prod_{i\in\sigma}\left(e^{x_i}-1\right)$.
\end{center}
\end{thm}

\begin{proof}
The proof is adapted from that of the ordinary Hilbert series found in \cite{MiS}. First, note that $\textbf{x}^\textbf{a}$ lies outside of $I_\Delta$ if and only if $\textbf{x}^{\text{supp}(\textbf{a})}$ lies outside of $I_\Delta$, where $\text{supp}(\textbf{a})=\{i\mid a_i\neq0\}$ is called the \textit{support} of $\textbf{a}$. Then, by the definition of the Stanley-Reisner ideal, the monomials that do not vanish in $S/I_\Delta$ are precisely those whose support is in $\Delta$. The result follows from the computation in Proposition 1 and the fact that the monomials $x^{\text{supp}(\textbf{a})}$ are square-free.
\end{proof}

This theorem begins to exhibit one of the chief differences between the ordinary Hilbert series and its exponential counterpart. In the ordinary case (see \cite{MiS}), the Hilbert series of a Stanley-Reisner ring can be written as
\begin{center}
$\displaystyle\frac{K(x_1,\dots,x_n)}{(1-x_1)(1-x_2)\dots(1-x_n)}$,
\end{center}
where $K(x_1,\dots,x_n)$ is a polynomial with integer coefficients (often called the $K$-\emph{polynomial} of $S/I_\Delta$). However, the exponential series relates to a different polynomial. Namely, the exponential Hilbert series of $S/I_\Delta$ is polynomial in the $e^{x_i}$. We may also note, as seen in Proposition 1, that the exponential Hilbert series of $S(-\textbf{a})$ is polynomial in the $x_i$ and the $e^{x_i}$. In either case, the exponential Hilbert series seems to converge to a polynomial outright, rather than in relation to a rational function. In the next subsection, we will find that this polynomial has nice structure and relates closely with the $f$-vector and $h$-vector of a simplicial complex.

\subsection{Coarsely-graded exponential Hilbert series}

In this subsection, we focus on the coarsely-graded exponential Hilbert series obtained by setting $x_i=t$ for all $i$. We then have
\begin{equation}
E(S/I_\Delta;t)=\displaystyle\sum_{\sigma\in\Delta}(e^t-1)^{|\sigma|}=\sum_{\sigma\in\Delta}(e^t-1)^{\dim(\sigma)+1}.
\end{equation}
Note again that this is polynomial in the $e^t$. The constant term of this polynomial will be
\begin{equation}
1-\#(\text{0-faces})+\#(\text{1-faces})-\#(\text{2-faces})+\dots=-\chi(\Delta),
\end{equation}
where $\chi(\Delta)$ is the Euler characteristic of $\Delta$. Note: for simplicity in notation, we are counting the empty face in the calculation of $\chi(\Delta)$. Then (2.2) follows from the fact that the number of terms with power $|\sigma|$ is equal to the number of faces of $\Delta$ with dimension equal to that of $\sigma$. The sum alternates because of the powers of $-1$ in the expansion. As before, we set $f_i=\#(\text{\emph{i}-faces})$ of $\Delta$. Recall that $f_{-1}=1$, as we are counting the empty face. Using this notation, we can rewrite (2.1) as follows:
\begin{equation}
E(S/I_\Delta;t)=\displaystyle\sum_{i=0}^d f_{i-1}(e^t-1)^i,
\end{equation}
where $d=\dim(\Delta)+1$.

Upon expansion, we get a polynomial of degree $d:=\dim(\Delta)+1$ in $y:=e^t$:
\begin{equation}
E(S/I_\Delta;t)=e_0+e_1y+e_2y^2+\dots+e_dy^d.
\end{equation}
We call the vector $(e_0,\dots,e_d)$ consisting of the coefficients of the polynomial in (2.4) the $e$-\textit{vector} of $\Delta$. We have already shown that $e_0=-\chi(\Delta)$. We next explore the remaining coefficients. Expanding $E(S/I_\Delta;t)$ yields
\begin{center}
$\displaystyle\sum_{i=0}^df_{i-1}(e^x-1)^i=\sum_{i=0}^df_{i-1}\sum_{j=0}^i(-1)^{i-j}{i\choose j}y^j$.
\end{center}
We wish to isolate the coefficient of $y^k$ for some fixed $k\in\{0,\dots,d\}$. The only values of $i$ which contribute a term to this coefficient are those where $i\geq k$. Therefore, the coefficient of $y^k=e^{kx}$ is
\begin{equation}
e_k=\displaystyle\sum_{i=k}^d(-1)^{i-k}f_{i-1}{i\choose k}.
\end{equation}
Note that there is an analogous formula for the components of the $h$-vector of $\Delta$ (see \cite{Stan96}), given below:
\begin{equation}
h_k=\displaystyle\sum_{i=0}^k(-1)^{k-i}f_{i-1}{d-i\choose k-i}.
\end{equation}

\section{The $e$-vector, the $f$-vector, and the $h$-vector}

We now explore the relationships between the three vectors. We begin with the relationship between the $e$-vector and $f$-vector. By (2.5), we can write the components of the $e$-vector in terms of the $f$-vector. Therefore, the $f$-vector determines the $e$-vector. A similar relationship exists in reverse.

\begin{thm}
The $f$-vector is determined by the $e$-vector.
\end{thm}
\begin{proof}
This basically follows from the linear relationship
\begin{equation}
e_k=\displaystyle\sum_{i=k}^d(-1)^{i-k}f_{i-1}{i\choose k},
\end{equation}
but we include the details, as we will use them later in this section. Equation (3.1) is a system of $d+1$ linear equations in $d+1$ unknowns. In matrix form, we have
\begin{gather}
	\begin{bmatrix} f_{-1} & f_0 & \dots & f_{d-1} \end{bmatrix}\begin{bmatrix} 1 & 0 & ... & 0 \\ a_{10} & 1 & ... & 0 \\ \vdots & \vdots & \vdots & \vdots \\ a_{d0} & a_{d1} & ... & 1 \end{bmatrix}
	=
	\begin{bmatrix} e_0 & e_1 & \dots & e_d \end{bmatrix}
\end{gather}
where, if $i\geq j$,
\begin{center}
$a_{ij}=(-1)^{i-j}\displaystyle{i\choose j}$.
\end{center}
Since this system is invertible and lower-triangular, it can be solved via back-substitution, and the $e$-vector determines the $f$-vector.
\end{proof}

Note that (3.2) allows us to compute a formula for the $f$-components in terms of the $e$-components. As we will use this computation later in this section, we again provide the details.

Let $A$ be the transformation matrix in (3.2). Then $A$ has the form
\begin{gather}
\begin{bmatrix}1 & 0 & 0 & \dots & 0 \\ -{1\choose0} & 1 & 0 & \dots & 0 \\ {2\choose0} &- {2\choose1} & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\(-1)^d{d\choose0} & (-1)^{d-1}{d\choose1} & (-1)^{d-2}{d\choose2} & \dots & 1 \end{bmatrix}
\end{gather}
The rows of $A$ consist of the entries of the corresponding rows of Pascal's Triangle, alternating in sign. Matrices of this form are known as \emph{Pascal matrices} (or, more accurately, $A$ is the inverse of a Pascal matrix). It is well-known that the inverse of $A$ is then given by $|A|$. Knowing the $e$-vector then allows us to compute the $f$-vector via the lower-triangular system
\begin{gather}
\begin{bmatrix} f_{-1} & f_0 & \dots & f_{d-1} \end{bmatrix}=\begin{bmatrix} e_0 & e_1 & \dots & e_d \end{bmatrix}\begin{bmatrix} 1 & 0 & 0 & \dots & 0 \\ 1 & 1 & 0 & \dots & 0 \\ 1 & 2 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\  {d\choose 0} &  {d\choose1} & {d\choose 2} & \dots & 1 \end{bmatrix}
\end{gather}
We sum this up with the following formula for the $f$-vector in terms of the $e$-vector:
\begin{equation}
f_{i-1}=\displaystyle\sum_{j=i}^d{j\choose i}e_j.
\end{equation}
This relationship is exhibited in the following example.
\vspace{1pc}
\\
\noindent\textbf{Example:} Let
\begin{center}
$\Delta=\{\{1\},\{2\},\{3\},\{4\},\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{3,4\},\{1,2,3\}\}$.
\end{center}
Then the $f$-vector is given by $(1,4,5,1)$. Using (3.1), we can easily compute the $e$-vector: $(1,-3,2,1)$. If we start with the $e$-vector, then we can again easily compute the $f$-vector, this time using (3.5).
\vspace{1pc}
\\
\indent Note that, as the $h$-vector determines the $f$-vector and vice versa, we have a similar relationship between the $h$-vector and the $e$-vector. Note that (2.6) can be used to write a lower-triangular system describing the relationship between the $h$-vector and the $f$-vector.
\begin{gather}
	\begin{bmatrix} 1 & 0 & 0 & \dots & 0 \\ b_{10} & 1 & 0 & \dots & 0 \\ b_{20} & b_{21} & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ b_{d0} & b_{d1} & b_{d2} & \dots & 1 \end{bmatrix}\begin{bmatrix} f_{-1} \\ f_0 \\ \vdots \\ f_{d-1} \end{bmatrix}
	=
	\begin{bmatrix} h_0 \\ h_1 \\ \vdots \\ h_d \end{bmatrix}
\end{gather}
where, for $i\geq j$
\begin{center}
$b_{ij}=(-1)^{i-j}\displaystyle{d-j\choose i-j}$,
\end{center}
and we denote the transformation matrix in (4.1) as $B$. Similarly to $A$, the inverse of $B$ is $|B|$.  Then $f^TA=e$ and $Bf=h$, where we denote the $e$-vector, $f$-vector, and $h$-vector by $e$, $f$, and $h$, respectively. Equivalently, $f^TB^T=h^T$. Then $f^T=h^T(B^T)^{-1}$, and we have
\begin{equation}
h^T(B^T)^{-1}A=e^T=h^T|B|^TA.
\end{equation}
Let $D=|B|^TA$. Then $d_{ij}=0$ if $i+j<d$ and
\begin{equation}
d_{ij}=(-1)^j{i+j-d\choose d-j},
\end{equation}
otherwise. This matrix is easier to use if we reverse the order of the columns to write it in lower-triangular form. Denote this lower-triangular matrix as $\widehat{D}$. Thus, the nonzero entries of $\widehat{D}$, have the form
\begin{equation}
\widehat{d}_{ij}=(-1)^{d-j}{i\choose j}.
\end{equation}
Multiplying $\widehat{D}$ on the right by the reverse $h$-vector, $(h_d,\dots,h_1,h_0)$, yields
\begin{equation}
e_{d-k}=\displaystyle\sum_{j=k}^d(-1)^{d-k}{j\choose k}h_j.
\end{equation}
Therefore, we have
\begin{equation}
e_k=\displaystyle\sum_{j=d-k}^d(-1)^k{j\choose d-k}h_j.
\end{equation}
Reindexing (4.6) by setting $l=j-d-k$ gives the following formula for the $e$-vector in terms of the $h$-vector:
\begin{equation}
e_k=\displaystyle\sum_{l=0}^k(-1)^k{d-k+l\choose d-k}h_{d-k+l}.
\end{equation}

\section{The $e$-vector and Property E}

We begin this section with a motivating example.
\vspace{1pc}
\\
\noindent\textbf{Example:} Let $\Delta$ be the boundary of the tetrahedron. This complex has $f$-vector $(1,4,6,4)$, $e$-vector $(-1,4,-6,4)$ and $h$-vector $(1,1,1,1)$. We note a few things from this calculation. The first is that the $e$-vector does not satisfy the Dehn-Sommerville equations, even when $\Delta$ is the boundary of a simplicial polytope. We also note that, in this example, the $e$-vector is an alternating version of the $f$-vector. This is no accident, as we will see in this section.
\vspace{1pc}
\\
Fixing a $(d-1)$-dimensional simplicial complex $\Delta$, we denote the $e$-components, $f$-components, and $h$-components of $\Delta$ as $e_i(\Delta)$, $f_{i-1}(\Delta)$, and $h_i(\Delta)$, respectively. We then define the following three polynomials. The \textit{$f$-polynomial} is defined to be $$f_\Delta(t)=\sum_{i=0}^d f_{i-1}(\Delta) t^i,$$ the \textit{$e$-polynomial} is defined to be $$e_\Delta(t)=\sum_{i=0}^d e_i(\Delta) t^i,$$ and finally the \textit{$h$-polynomial} is defined to be $$h_\Delta(t)=\sum_{i=0}^d h_i(\Delta) t^i.$$

If the simplicial complex $\Delta$ is understood, then we sometimes omit the subscript. The relationship between the $f$-polynomial and $h$-polynomial is classically given by $$h_\Delta(t)=(1-t)^df_\Delta\left(\frac{t}{1-t}\right).$$ From equations (2.3) and (2.4), it follows that $e_\Delta(t)=f_\Delta(t-1)$, and hence $$h_\Delta(t)=(1-t)^d e_\Delta\left(\frac{1}{1-t} \right).$$

Note that $e_\Delta(0)=e_0=-\chi(\Delta)$ and $e_\Delta(1)=f_\Delta(0)=f_{-1}=1$. This implies that $$\sum_{i=1}^d e_i=1+\chi(\Delta)=\sum_{i=0}^{d-1} (-1)^i f_i=\tilde{\chi}(\Delta),$$ where $\tilde{\chi}(\Delta)$ is the ordinary topological Euler characteristic of $\Delta$ (ignoring the empty face). Combining this observation with the above example motivates the following definition.

\begin{defin} We say that a $(d-1)$-dimensional simplicial complex $\Delta$ has \textit{Property E} if for every $0\leq k\leq d$ we have that $e_k=(-1)^{d-k} f_{k-1}$. If these equalities are just required to hold for $1\leq k\leq d$, then we say that $\Delta$ has \textit{weak Property E}.
\end{defin}

\begin{remark}
Note that, in terms of the $e$-polynomial, Property E just says that $e_\Delta(t)=(-1)^df_\Delta(-t)$, while weak Property E is equivalent to the equation $e_\Delta(t)+(-1)^{d+1}f_\Delta(-t)=e_0+(-1)^{d+1}$. Also note that Property E implies that $e_0=-\chi(\Delta)=(-1)^d$, which in turn implies that $\Delta$ has the topological Euler characteristic of a $(d-1)$-sphere. Hence Property E is very restrictive. We introduce the notion of weak Property E to allow for more simplicial complexes.
\end{remark}

We begin by proving results which will allow us to furnish many examples of simplicial complexes satisfying Property E or weak Property E. The first proposition gives a local check to see if a simplicial complex has weak Property E. Recall that the link of a vertex $v$ in $\Delta$ is defined to be the following $(d-2)$-dimensional subcomplex of $\Delta$: $$\Lk v:=\{\sigma\in\Delta\mid \sigma\cup \{v\}\in\Delta\text{ and } v\notin\sigma \}.$$

\begin{prop}
Suppose that for every $v\in \text{vert}(\Delta)$ we have that $\Lk v$ has Property E. Then $$e_\Delta(t)+(-1)^{d+1}f_\Delta(-t)=e_0+(-1)^{d+1} .$$ In particular, $\Delta$ has weak Property E.
\end{prop}
\begin{proof} Since every $j$-dimensional simplex of $\Delta$ has $j+1$ vertices, it follows that $$(j+1)f_j(\Delta)=\sum_{v\in \text{vert}(\Delta)} f_{j-1}(\Lk v).$$ Rewriting this in terms of the $f$-polynomial, we have that $$\frac{d}{dt} f_\Delta(t)=\sum_{v\in \text{vert}(\Delta)} f_{\Lk v}(t).$$

As $e_\Delta(t)=f_\Delta(t-1)$, it follows that the $e$-polynomial has the same property:

$$\frac{d}{dt}e_\Delta(t)=\frac{d}{dt} f_\Delta(t-1)=\sum_{v\in \text{vert}(\Delta)} f_{\Lk v}(t-1)=\sum_{v\in \text{vert}(\Delta)} e_{\Lk v}(t).$$

Now, suppose that for every $v\in \text{vert}(\Delta)$ we have that $\Lk v$ has Property E. In other words, $$e_{\Lk v}(t)=(-1)^{d-1} f_{\Lk v}(-t).$$

Hence $$\frac{d}{dt}e_\Delta(t)=\sum_{v\in \text{vert}(\Delta)} e_{\Lk v}(t)=\sum_{v\in \text{vert}(\Delta)} (-1)^{d-1} f_{\Lk v}(-t)=(-1)^d \frac{d}{dt} f_\Delta(-t).$$

This implies that $e_\Delta(t)=(-1)^d f_\Delta(-t)+C$. Plugging in $t=0$ to solve for the constant, we obtain $C=(-1)^{d+1}f_{-1}+e_0=(-1)^{d+1}-\chi(\Delta)$, and the result follows.

\end{proof}

We now prove the main theorem of this section, which says that (weak) Property E on the $e$-vector is equivalent to the (general) Dehn-Sommerville condition on the $h$-vector. This means that, in certain situations, the $e$-vector has more in common with the $h$-vector than originally anticipated. Recall that if the $h$-vector satisfies the classical Dehn-Sommerville equations, then $h_k=h_{d-k}$ (so, in particular, $h$ is symmetric). The $h$-vector satisfies the general Dehn-Sommerville equations if
\begin{equation}
h_k-h_{d-k}=(-1)^k {d\choose k}\left(\tilde{\chi}(S^{d-1})-\tilde{\chi}(\Delta) \right),
\end{equation}
where $\tilde{\chi}(S^{d-1})=1+(-1)^{d-1}$ is just the Euler characteristic of the $(d-1)$-sphere.

\begin{remark} The general Dehn-Sommerville equations are sometimes referred to as Klee's Dehn-Sommerville equations, as they were originally considered by V. Klee in \cite{Kle}.\end{remark}

\begin{thm}
A $(d-1)$-simplicial complex $\Delta$ has weak Property E if and only if for every $0\leq k\leq d$ we have that $$h_k-h_{d-k}=(-1)^k {d\choose k}\left(\tilde{\chi}(S^{d-1})-\tilde{\chi}(\Delta) \right).$$

In particular, $\Delta$ has Property E if and only if for every $0\leq k\leq d$ we have that $h_k=h_{d-k}$.
\end{thm}

\begin{proof}
We restate the conditions of the theorem in terms of polynomials. Recall that a simplicial complex has weak Property E if and only if $$e_\Delta(t)+(-1)^{d+1}f_\Delta(-t)=e_\Delta(t)+(-1)^{d+1} e(1-t)=e_0+(-1)^{d+1}.$$

In terms of the $h$-polynomial, the generalized Dehn-Sommerville condition on the $h$-vector in the theorem is equivalent to $$h(t)-t^d h\left(\frac{1}{t}\right)=C\cdot K(t),$$

where $C=1-\tilde{\chi}(\Delta)+(-1)^{d+1}=e_0+(-1)^{d+1}$ and $$K(t)=\sum_{k=0}^d (-1)^k {d \choose k} t^k. $$

In terms of the $e$-polynomial, the $h$-polynomial equation can be rewritten as $$(1-t)^de\left(\frac{1}{1-t}\right)-(t-1)^d e\left(\frac{t}{t-1}\right)=C\cdot K(t).$$

Factoring $(1-t)^d$ from the left of the equation and moving it to the right-hand side, the above equation becomes:

$$e\left(\frac{1}{1-t}\right)+(-1)^{d+1} e\left(\frac{t}{t-1}\right)=C\cdot \frac{K(t)}{(1-t)^d}.$$

Making the substitution $t=1-\frac{1}{u}$, we obtain $$e(u)+(-1)^{d+1} e(1-u)=C\cdot u^d K\left(\frac{u-1}{u} \right).$$

We have that $u^d K\left(\frac{u-1}{u} \right)=1$, as $$u^d K\left(\frac{u-1}{u} \right)=\sum_{k=0}^d (-1)^k {d\choose k} \left(\frac{u-1}{u} \right)^k u^d=\sum_{k=0}^d {d\choose k} (1-u)^k u^{d-k}=1 .$$

Note that the right-most equality is an application of the Binomial Theorem. Thus our equation of interest finally becomes $$e(u)+(-1)^{d+1} e(1-u)=C=e_0+(-1)^{d+1}.$$

This computation shows that the general Dehn-Sommerville condition on the $h$-vector is equivalent to weak Property E, and completes the proof of the first part of the theorem.

The second part of the theorem now follows from the first. Note that if $\Delta$ has Property E, then it has weak Property E. Furthermore, Property E implies that $\tilde{\chi}(\Delta)=\tilde{\chi}(S^{d-1})$ (see the previous remark), and hence for every $0\leq k\leq d$ we have that $h_k=h_{d-k}$. If we assume that for every $0\leq k\leq d$ we have that $h_k=h_{d-k}$, then $\tilde{\chi}(\Delta)=\tilde{\chi}(S^{d-1})$ and $\Delta$ has weak Property E, and thus $\Delta$ has Property E.
\end{proof}

Theorem 3 can be summed up as saying that, in the case where $\Delta$ satisfies the general Dehn-Sommerville equations, the exponential Hilbert series of $\Delta$ encodes precisely the same information as the $f$-vector of $\Delta$.

We will now exploit Theorem 3 to furnish many examples of simplicial complexes satisfying Property E. First, we recall a few definitions. A simplicial complex is \textit{pure} if every maximal face has the same dimension. A pure $(d-1)$-simplicial complex $\Delta$ is \textit{Eulerian} if for every simplex (except the empty simplex) $\sigma\in \Delta$ we have that $\tilde\chi(\Lk \sigma)=1+(-1)^{d+\dim\sigma}$ (as before, $\Lk\sigma$ denotes the link of $\sigma$ in $\Delta$). Note that this definition just requires that the link of every face (except the empty face) of $\Delta$ has the same Euler characteristic as a sphere of appropriate dimension. If an Eulerian $\Delta$ additionally satisfies $\tilde\chi(\Delta)=1+(-1)^{d-1}$, then $\Delta$ is an \textit{Eulerian sphere}.

\begin{cor}
If $\Delta$ is Eulerian then $\Delta$ has weak Property E. If $\Delta$ is further assumed to have odd dimension or is a Eulerian sphere, then $\Delta$ has Property E.
\end{cor}
\begin{proof}
It was shown in \cite{Kle} that if $\Delta$ is Eulerian, then the $h$-vector satisfies the general Dehn-Sommerville equations. Hence $\Delta$ has weak Property E by the first part of Theorem 3. If $\Delta$ is an Eulerian sphere, then $\tilde{\chi}(\Delta)=\tilde{\chi}(S^{d-1})$, and hence $\Delta$ has Property E by the second part of Theorem 3. If $\Delta$ has odd dimension, then \cite[Lemma 17.3.3]{Dav} implies that $\tilde{\chi}(\Delta)=0$. So an odd-dimensional Eulerian $\Delta$ is an Eulerian sphere, and hence has Property E.
\end{proof}

\begin{remark}
One does not need the full general Dehn-Sommerville to deduce that an Eulerian $\Delta$ has weak Property E. Instead, one can apply Proposition 2 as follows. It is a standard fact that a complex $\Delta$ is Eulerian if and only if the link of every vertex is an Eulerian sphere. Hence the second part of Theorem 3 implies that the link of every vertex has Property E, and therefore by Theorem 3, $\Delta$ has weak Property E.
\end{remark}

\begin{remark}
If $\Delta$ is Eulerian, then by \cite[Theorem 1]{Aki}, $\tilde{\chi}(\Delta)=f_\Delta\left(-\frac{1}{2}\right)=e_\Delta\left(\frac{1}{2}\right)$. If $\Delta$ is odd-dimensional, then as in the proof of Corollary 1, we have that $\tilde{\chi}(\Delta)=0$. It follows that $t=\frac{1}{2}$ is a root of $e_\Delta(t)$, and hence $t=-\ln 2$ is a root of the exponential Hilbert series.
\end{remark}

Corollary 1 provides a plethora of examples of complexes satisfying Property E. For example, it follows that if $\Delta$ is a simplicial polytope or is a triangulation of your favorite odd-dimensional manifold, then $\Delta$ has Property E. The following example completely characterizes $1$-dimensional complexes with Property E, and shows that the converse of each of the parts of the above corollary is false.
\vspace{1pc}
\\
\noindent\textbf{Example:} Suppose that $\Delta$ is $1$-dimensional and connected. Then $e_0=-\chi(\Delta)=1-f_0+f_1$, $e_1=f_0-2f_1$ and $e_2=f_1$. If $\Delta$ has weak Property E, then it follows that $e_1=-f_0$, and therefore $f_0=f_1$. This means that $\chi(\Delta)=-1$, and hence $\tilde{\chi}(\Delta)=0$. So for $1$-dimensional $\Delta$, Property E and weak Property E are equivalent.

If $\tilde{\chi}(\Delta)=0$, then it is homotopic to a cycle. Any such $\Delta$ looks like a cycle with trees attached to its vertices, which clearly satisfies $f_0=f_1$. It follows that a connected $1$-dimensional $\Delta$ satisfies Property E if and only if it is a cycle with trees emanating from its vertices.

Consider such a $\Delta$ which is an empty triangle with an extra edge attached to one of its vertices. This $\Delta$ has Property E, but is not Eulerian, as the links of the vertices of the extra edge do not have the correct Euler characteristic.
\vspace{1pc}
\\
The following proposition allows one to produce many more examples of complexes with Property E.

\begin{prop}
Suppose that $\Delta=\Delta_1\ast\Delta_2$ is the join of two simplicial complexes $\Delta_1$ and $\Delta_2$ satisfying Property E. Then $\Delta$ has Property E.
\end{prop}
\begin{proof}
We have that $f_\Delta(t)=f_{\Delta_1}(t)f_{\Delta_2}(t)$. As $e_\Delta(t)=f_\Delta(t-1)$, it follows that $e_\Delta(t)=e_{\Delta_1}(t)e_{\Delta_2}(t)$. Suppose that $\Delta_1$ is $l$-dimensional and $\Delta_2$ is $m$-dimensional (so that $\Delta$ is $l+m+1$-dimensional). As both $\Delta_1$ and $\Delta_2$ have Property E, we have that $e_{\Delta_1}(t)=(-1)^{l+1}f_{\Delta_1}(-t)$ and $e_{\Delta_2}(t)=(-1)^{l+1}f_{\Delta_2}(-t)$. It follows that $e_\Delta(t)=(-1)^{l+m+2}f_{\Delta_1}(-t)f_{\Delta_2}(-t)=(-1)^{l+m+2}f_{\Delta}(-t)$, and therefore $\Delta$ has Property E.
\end{proof}

By taking iterated suspensions of the complexes in the previous example, the above proposition allows one to produce non-Eulerian complexes satisfying Property E in every dimension. Hence (via Theorem 3) there are many non-Eulerian complexes satisfying the classical Dehn-Sommerville relations. In general, a characterization of simplicial complexes with (weak) Property E would be interesting. But, Theorem 3 says that characterizing simplicial complexes with Property E is equivalent to characterizing simplicial complexes with symmetric $h$-vectors, which is known to be a difficult problem.

\end{document}


TITLE: If $a$, $b$, $c \geq 1$; $y \geq x \geq 1$; $p$, $q$, $r > 0$ Prove the insane inequality
QUESTION [5 upvotes]: $$\left(\frac{1+y\left(a^pb^qc^r\right)^{\frac{1}{p+q+r}}}{1+x\left(a^pb^qc^r\right)^{\frac{1}{p+q+r}}}\right)^{\frac{p+q+r}{\left(a^pb^qc^r\right)^{\frac{1}{p+q+r}}}}\left(\frac{1+xa}{1+ya}\right)^{\frac{p}{a}}\left(\frac{1+xb}{1+yb}\right)^{\frac{q}{b}}\left(\frac{1+xc}{1+yc}\right)^{\frac{r}{c}}\geq \prod \limits_{cyc}\left(\frac{1+y\left(a^pb^q\right)^{\frac{1}{p+q}}}{1+x\left(a^pb^q\right)^{\frac{1}{p+q}}}\right)^{\frac{p+q}{\left(a^pb^q\right)^{\frac{1}{p+q}}}}$$
This is a inequality problem from 2019 Jozsef Wildt International Mathematics Competition. For this problem i almost tried in all ways with AM-GM and Cauchy-Schwarz but i am unable to do it. Honestly i don't even know how to start thinking for this problem. Please help. I know i have not uploaded my attempts. But what i shall attempt. I am completely blank about this problem

REPLY [3 votes]: We need to prove that $g(y)\geq0,$ where
$$g(y)=\tfrac{p+q+r}{\left(a^pb^qc^r\right)^{\tfrac{1}{p+q+r}}}\ln\tfrac{1+y\left(a^pb^qc^r\right)^{\tfrac{1}{p+q+r}}}{1+x\left(a^pb^qc^r\right)^{\tfrac{1}{p+q+r}}}+\sum_{cyc}\tfrac{p}{a}\ln\tfrac{1+ya}{1+xa}-\sum_{cyc}\tfrac{p+q}{\left(a^pb^q\right)^{\tfrac{1}{p+q}}}\ln\tfrac{1+y\left(a^pb^q\right)^{\tfrac{1}{p+q}}}{1+x\left(a^pb^q\right)^{\tfrac{1}{p+q}}}.$$
But $$g'(y)=\tfrac{p+q+r}{1+y\left(a^pb^qc^r\right)^{\tfrac{1}{p+q+r}}}+\sum_{cyc}\tfrac{p}{1+ya}-\sum_{cyc}\tfrac{p+q}{1+y\left(a^pb^q\right)^{\tfrac{1}{p+q}}}=$$
$$=\frac{p+q+r}{1+ye^{\frac{\sum\limits_{cyc}p\ln{a}}{p+q+r}}}+\sum_{cyc}\frac{p}{1+ye^{\ln{a}}}-\sum_{cyc}\frac{p+q}{1+ye^{\frac{p\ln{a}+q\ln{b}}{p+q}}}.$$
Now, let $f(t)=\frac{1}{1+ye^t},$ where $t\geq0$ and $y\geq1$.
Thus, $$f''(t)=-\left(\frac{ye^t}{(1+ye^t)^2}\right)'=-\left(\frac{ye^t+1-1}{(1+ye^t)^2}\right)'=$$
$$=\frac{ye^t}{(1+ye^t)^2}-\frac{2ye^t}{(1+ye^t)^3}=\frac{ye^t(ye^t-1)}{(1+ye^t)^3}\geq0,$$ which says that $f$ is a convex function.
Thus, by the Tiberiu Popoviciu's inequality $g'(y)\geq0,$ which says $$g(y)\geq g(x)=0$$ and we are done!
About Popoviciu see here: https://arxiv.org/pdf/0803.2958v1.pdf


TITLE: Geometric or Poisson
QUESTION [2 upvotes]: Drought length is referred to as the number of consecutive time intervals in which the water supply remains below a critical value. Consider the drought length as a random variable, denoted as $Y$, which is assumed to have a geometric distribution with $p = 0.409$

What is the probability that a drought lasts exactly $3$ intervals? $(0.0844)$
What is the probability that a drought lasts at most 3 intervals? $(0.878)$

My try:

$(0.409)^3 = 0.06841$.
$(0.409)^3 + (0.409)^2 +(0.409)^1 +(0.409)^0$.

REPLY [1 votes]: The geometric distribution is defined as
$$P(Y=k)=p(1-p)^{k-1},\quad k\geq 1$$
Equivalently:
$$P(Y>k)=(1-p)^k$$
The first question just asks $P(Y=3)$, and the second question asks $P(Y\leq 3)$, which we can write $1-P(Y>3)$.


TITLE: Condition for strong law of large numbers : Understanding the solution
QUESTION [0 upvotes]: I am reading the solution of the following task:

Here is the solution:

From where does the last inequality in the second line comes from? Everything else is totally clear to me.

REPLY [2 votes]: Compare the sum with an integral:
$$\sum_{i=1}^n i^{-3/2} = 1+\sum_{i=2}^n i^{-3/2} \leq 1+\int_1^n x^{-3/2}\ dx$$
Edit: As @Did correctly notes, the stated inequality (which is incorrect) does not follow from this.


TITLE: Simplifying expressions with rational exponents
QUESTION [0 upvotes]: So I only half understand this concept, the question is
Simplify $2(x^2+8)^{\frac85} + x \cdot 3(x^2 + 8)^{\frac35} \cdot 9x$
The steps I have so far are
$2(x^2+8)^{\frac85} + 27x^2(x^2 + 8)^{\frac35}$
$(x^2+8)^\frac35[$
After the bracket is where I'm stuck at conceptually. What am I doing with the $27x^2$ and the $2?$ Am I adding them together?

REPLY [1 votes]: You're not doing anything with $27x^2$ and $2$ just yet. You will keep them inside the brackets, along with some other stuff, as a result of factoring out $(x^2+8)^{\frac{3}{5}}$; you'll simplify the expression in the brackets after that.
Your main goal right now is to factor. Remember that factoring is effectively division (in each term). For example, if you factor $x^2$ out of $x^5$ you will be left with $x^3$, i.e. you would write $x^5=x^2\cdot x^3$. Why? Because $\displaystyle \frac{x^5}{x^2}=x^3$, giving you the remaining factor for $x^5=x^2\cdot(\text{?})$.
Same here. To factor $(x^2+8)^{\frac{3}{5}}$ out of $(x^2+8)^{\frac{8}{5}}$ means to divide:
$$\frac{(x^2+8)^{\frac{8}{5}}}{(x^2+8)^{\frac{3}{5}}}=(x^2+8)^{\frac{8}{5}-\frac{3}{5}}=(x^2+8)^1=x^2+8,$$
so your expression simplifies to
$$2(x^2+8)^{\frac{8}{5}} + 27x^2(x^2 + 8)^{\frac{3}{5}}=(x^2 + 8)^{\frac{3}{5}}\left[2(x^2+8)+27x^2\right].$$
I hope you can take it from here.


TITLE: If $G \cong H \times \mathbb{Z}_2$, show that $G$ contains an element $a$ of order $2$ with the property that $ag = ga$ for all $g \in G$.
QUESTION [1 upvotes]: I have so far that there is one element in $H \times \mathbb{Z}_2$ with order two which commutes with everything else in that group, namely $(e_H, 1)$. This is presuming that $\mathbb{Z}_2$ is a group under addition.
However, I can't see why this means that $G$ must also contain an element with the same property. Should this be the next stage of my proof or am I heading in the wrong direction?

REPLY [1 votes]: I think I have found a correct answer to my own question.
If $\phi: G \rightarrow H \times \mathbb{Z}_2$ is the isomorphism and $(e_H, 1) \in \mathbb{Z}_2 $ has order $2$, then $\phi(a) = (e_H, 1)$ for some $a$ in $G$. Then $\phi(a^2) = (e_H,0)$ which means that $a^2 = e_G$ since the kernel must contain only $e_G$. Then $a$ must have order $2$.
Secondly take any $g \in G$. I have $\phi(ag) = (e_H,1)(h,n) = (h,n)(e_H,1) = \phi(ga)$ for some $h \in H$ and $n \in \mathbb{Z}_2$, since the identity commutes with everything and the additive group $\mathbb{Z}_2$ is commutative. Then since $\phi$ is injective, this must mean that $ag$ = $ga$.


TITLE: Linear Algebra Question. Invertibility Problem.
QUESTION [0 upvotes]: $A$ is a $d*k$ full rank matrix, given d > k. Is the matrix $I-AA^T$ invertible?

REPLY [0 votes]: $A A^T$ is positive semidefinite (assuming this is over the reals).  If $\lambda > 0$ is an eigenvalue of $A A^T$,
replace $A$ by $\lambda^{-1/2} A$ to get a counterexample.


TITLE: Constrained Optimisation Problem: Confusion with Algebra/Contradiction
QUESTION [1 upvotes]: I completed the following constrained optimisation problem:

Maximum and minimum values of $f(x,y) = x^2 + 2xy + y^2$ on the ellipse $g(x,y) = 2x^2 + y^2 - xy - 4x = 0$.

$\nabla f = \lambda \nabla g$
$\therefore (2x + 2y, 2x + 2y) = \lambda(4x - y - 4, 2y - x)$
We have a system of 3 equations in 3 unknowns:
$2x + 2y = \lambda(4x - y - 4)$,
$2x + 2y = \lambda(2y - x)$,
$2x^2 + y^2 - xy - 4x = 0$.
$\\$
$2x + 2y = \lambda(4x - y - 4)$
$\implies \lambda = \dfrac{2x + 2y}{4x - y - 4} \forall \ 4x - y - 4 \not= 0$
$\\$
$2x + 2y = \lambda(2y - x)$
$\implies \dfrac{2x + 2y}{2y - x} \forall \ 2y - x \not= 0$
$\\$
$\therefore \dfrac{2x + 2y}{4x - y - 4} = \dfrac{2x + 2y}{2y - x} \forall \ y \not= \dfrac{x}{2}, y \not= 4x - 4$ Remember this part: This is where my confusion lies.
But if we continue with our reasoning, we get the following (correct) points of potential maxima/minima:
$(x,y) = (0,0)$, $(x,y) = (1, -1)$, $(x,y) = (2,2)$, and $(x,y) = \left(\dfrac{2}{7}, \dfrac{-6}{-7}\right)$.
And, finally, using these points we find that $f_{max} = 16$ at $(x,y) = (2,2)$, and $f_{min} = 0$ at $(x,y) = (0,0)$ and $(x,y) = (1,-1)$.
But here's the problem: We had above that $y \not= \dfrac{x}{2}$; therefore, $(x,y) = (0,0)$ would get us $0 \not= \dfrac{0}{2} \implies 0 \not= 0$, which is obviously false. Also, as we just saw, $(0,0)$ is a solution for $f_{min}$!
The algebra here is confusing me, since we cannot have $y = \dfrac{x}{2}$, but $(0,0)$ is apparently the minima. Is this not a contradiction? Did I do something wrong? Or am I supposed to discard the solution $(0,0)$ and just have $f_{min} = 0$ at $(1, -1)$? What am I misunderstanding?
I would greatly appreciate it if people could please take the time to clarify this.

REPLY [0 votes]: First note that the feasible set is compact, so the $\max,\min$ exist. Since $Dg((x,y)) \neq 0$ for all $Ix,y)$ satisfying the constraints, we know that the Lagrange conditions apply (in particular, the solution is not determined completely by $g$). Hence
all solutions (and some more) can be determined by solving the Lagrange equations.
Second, note that you don't need to solve for $\lambda$.
If $\lambda = 0$ then you have $x=-y$ and substituting this into the
constraint gives $y \in \{  -1,0 \} $ which correspond to a value of $0$.
If $\lambda \neq 0$ then you have $5x-3y-4=0$, from which you can solve for $x={ 1\over 5}(3x+4)$, and substituting this into the
constraint gives $y \in \{  -{6 \over 7},2 \} $ which correspond to values of $({4 \over 7})^2, 4^2$.
Hence the $\min$ is $0$ and the $\max$ is $4^2$.


TITLE: Sum of power series $\sum_{n\geq0}\frac{n^2}{7^n}$
QUESTION [6 upvotes]: I'm having trouble with this power series : $$
\sum_{n\geq0}\frac{n^2}{7^n}$$
I have to solve it using differentiation/integration. I guess I have to approach it as $\sum_{n\geq0}n^2x^n$, where $x = \frac{1}{7}$ but I'm kinda lost as to what to do next.
Thanks in advance!

REPLY [14 votes]: Take $$\frac 1{1-x}=1+x+x^2+\cdots$$
Differentiate and multiply by $x$. Repeat once more. Profit.
ADD In general, let $D=x\frac{d}{dx}$ mean "differentiate then multiply by $x$", and let $D^k$ mean "do it $k$ times". Then $$D^k\frac{1}{1-x}=\sum_{n=1}^\infty n^kx^n$$
We have the following first cases:
$$\eqalign{
  & \frac{1}{{1 - x}} = {D^0}\frac{1}{{1 - x}}  \cr
  & \frac{x}{{{{\left( {1 - x} \right)}^2}}} = {D^1}\frac{1}{{1 - x}}  \cr
  & \frac{{{x^2} + x}}{{{{\left( {1 - x} \right)}^3}}} = {D^2}\frac{1}{{1 - x}}  \cr
  & \frac{{{x^3} + 4x + x}}{{{{\left( {1 - x} \right)}^4}}} = {D^3}\frac{1}{{1 - x}} \cr} $$
The numbers that pop up on the left hand side, $1;1,1;1,4,1;\dots$ are the Eulerian numbers
ADD${}^*$ There is an alternative way of obtaining the expansion of  $$\sum_{n=1}^\infty n^kx^n$$ directly, and is by means of the so called falling factorial:
$$x^{\underline{n}}=x(x-1)\dots (x-n+1)$$
We have that $$x^k=\sum_{i=0}^k \left\{\begin{matrix} k \\ i\end{matrix}\right\}x^{\underline{i}}$$
where the "curly" binomials are the Stirling numbers of the second kind, which count the number of ways of partitioning a $k$ object set into $i$ nonempty sets. If you let $x=n$, we get that $$\begin{align}
  {n^k}{x^n} = \sum\limits_{i = 0}^k \left\{\begin{matrix} k \\ i\end{matrix}\right\}n\left( {n - 1} \right) \cdots \left( {n - i + 1} \right){x^n} \\
  \sum\limits_{n > 1} {{n^k}{x^n}}  = \sum\limits_{i = 0}^k\left\{\begin{matrix} k \\ i\end{matrix}\right\}\sum\limits_{n > 1} n\left( {n - 1} \right) \cdots \left( {n - i + 1} \right){x^n}  \\
   = \sum\limits_{i = 0}^k \left\{\begin{matrix} k \\ i\end{matrix}\right\}\sum\limits_{n \geq  i} n\left( {n - 1} \right) \cdots \left( {n - i + 1} \right){x^n}  \\
 = \sum\limits_{i = 0}^k \left\{\begin{matrix} k \\ i\end{matrix}\right\}x^i\sum\limits_{n \geq  i} n\left( {n - 1} \right) \cdots \left( {n - i + 1} \right){x^{n-i}}  \\
   = \sum\limits_{i = 0}^k \left\{\begin{matrix} k \\ i\end{matrix}\right\}{x^i}\frac{d^i}{dx^i}\frac{1}{1 - x}  \end{align} $$
so you can express your sum in terms of the "plain" derivatives.


TITLE: What is a Jordan Cell?
QUESTION [0 upvotes]: Google has been surprisingly unhelpful for me.
A homework problem from my algebra class asks me to
Calculate p(A) where A is a Jordan cell and p is a polynomial.

I'd like to attempt the problem on my own, but I admit that without an inkling of what a "Jordan cell" is, this task seems rather daunting.
A simple definition an undergraduate student taking a course in algebra can understand would be much appreciated.

REPLY [1 votes]: To calculate $p(A)$, first calculate $A^k$ for all $k$. For
$$A=\begin{pmatrix}\lambda &1&0&\cdots &0\\ 0&\lambda&1&\cdots&0\\
\vdots&&\ddots&&\vdots\\0&0&0&&1\\0&0&0&\cdots&\lambda\end{pmatrix}$$
You can prove by induction that $A^k=(b_{i,j}^k)_{i,j}$ where $b_{i,j}^k=\binom{k}{j-i}\lambda^{k-(j-i)}$. (remember that $\binom{k}{j-i}=0$ when $j-i<0$ or $j-i>k$)
From here finding $p(A)=a_kA^k+...+a_1A+a_0I$ is easy.