text:
\begin{document}

\def\prof{{\sc Proof.\ \ }}
\def\sect#1{\begin{center}\section{#1}\end{center}}
\def\R#1{{\bf R}^{#1}}
\def\I#1#2{\int\limits_{#1}#2}
\def\p#1{#1^{\prime}}
\def\l#1#2#3{\lim_{#1 \rightarrow #2}#3}
\def\ld#1#2#3{\liminf_{#1 \rightarrow #2}#3}
\def\lu#1#2#3{\limsup_{#1 \rightarrow #2}#3}
\def\E#1#2{{\bf E}^{#1}\left(#2\right)}
\def\P#1#2{{\bf P}^{#1}\left(#2\right)}
\def\Pt#1#2#3{{\bf P}(#1,#2,#3)}
\def\pb#1{{\bf P}\left(#1\right)}
\def\eb#1{{\bf E}\left(#1\right)}
\def\Di#1{\,Dim\,#1}
\def\di#1{\,dim\,#1}
\def\fr#1#2{\frac{#1}{#2}}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}

\def\bea{\begin{eqnarray}}
\def\bean{\begin{eqnarray*}}
\def\eean{\end{eqnarray*}}
\def\eea{\end{eqnarray}}
\def\heq#1#2#3{\hbox to \hsize{\hskip #1 $#2$ \hss (#3)}}
\def\df#1#2{\frac{\displaystyle #1}{\displaystyle #2}}

\def\bdes{\begin{description}}
\def\ndes{\end{description}}

\newcommand{\bh}{{\bf h}}
\newcommand{\hf}{{\bf f}}
\newcommand{\he}{{\bf e}}
\newcommand{\hL}{{\bf L}}
\newcommand{\hg}{{\bf g}}
\newcommand{\hG}{{\bf G}}
\newcommand{\hM}{{\bf M}}

\newcommand{\bb}{\mathbb{b}}
\newcommand{\ww}{\mathbb{W}}
\newcommand{\hh}{\mathbb{H}}
\newcommand{\dd}{\mathbb{D}}
\newcommand{\cc}{\mathbb{C}}
\newcommand{\ee}{\mathbb{E}}
\newcommand{\zz}{\mathbb{Z}}
\newcommand{\nn}{\mathbb{N}}

\newcommand{\pp}{\mathbb{P}}
\newcommand{\qq}{\mathbb{Q}}
\newcommand{\ttt}{\mathbb{T}}

\def\rr{\Bbb R}
\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\s{\sigma}
\def\ep{\epsilon}
\def\d{\delta}
\def\D{\Delta}
\def\o{\omega}
\def\O{\Omega}
\def\n={\not=}
\def\u>{\wedge}
\def\d>{\vee}
\def\.{\bullet}
\def\l{\lambda}
\def\L{\Lambda}
\def\r{\rho}
\def\vf{\varphi}

\def\f{\phi}
\def\t{\tau}
\def\z{\zeta}
\def\na{\nabla}

\def\B{{I\!\!B}}
\def\E{{I\!\!E}}
\def\N{{I\!\!N}}
\def\P{{I\!\!P}}
\def\Q{{I\!\!\!Q}}
\def\R{{I\!\!R}}

\def\AA{\mathcal A}
\def\BB{\mathcal B}
\def\CC{\mathcal C}
\def\DD{\mathcal D}
\def\FF{\mathcal F}
\def\EE{\mathcal E}
\def\GG{\mathcal G}
\def\JJ{\mathcal J}
\def\LL{\mathcal L}
\def\NN{\mathcal N}
\def\PP{\mathcal P}
\def\SS{\mathcal S}

\def\Fht{\hbox{${\cal F}_{t}$}}
\def\Ght{\hbox{${\cal G}_{t}$}}

\def\U{\bigcup}
\def\Uu{\bigcap}
\def\Au{\forall}
\def\Eu{\exists}
\def\8u{\infty}
\def\0{\emptyset}
\def\mp{\longmapsto}
\def\rt{\rightarrow}
\def\up{\uparrow}
\def\dn{\downarrow}
\def\sub{\subset}
\def\vep{\varepsilon}
\def\ln{\langle}
\def\rn{\rangle}

\def\<<{\langle\!\langle}
\def\>>{\rangle\!\rangle}
\def\3|{|\!|\!|}
\def\ess{\text{\rm{ess}}}
\def\beg{\begin}

\def\beqt{\begin{equation}}
\def\neqt{\end{equation}}
\def\beq{\begin{equation}}
\def\neq{\end{equation}}

\def\bdes{\begin{description}}
\def\ndes{\end{description}}

\def\Ric{\text{\rm{Ric}}}
\def\Hess{\text{\rm{Hess}}}
\def\i{\text{\rm{i}}}
\def\ii{\text{\rm{ii}}}
\def\iii{\text{\rm{iii}}}
\def\iv{\text{\rm{iv}}}
\def\v{\text{\rm{v}}}
\def\vi{\text{\rm{vi}}}
\def\vii{\text{\rm{vii}}}
\def\viii{\text{\rm{viii}}}
\def\e{\text{\rm{e}}}

\def\Ra{\Rightarrow}
\def\Lra{\Leftrightarrow}
\def\rto{\longrightarrow}
\def\la{\leftarrow}
\def\ra{\rightarrow}
\def\ua{\uparrow}
\def\da{\downarrow}

\title{The existence of a strongly polynomial time simplex algorithm for linear programming problems
\thanks{Supported by the National Natural Science Foundation of China (11871118).}}

\author{Zi-zong Yan, Xiang-jun Li and Jinhai Guo \thanks{School of Information and Mathematics,
Yangtze University, Jingzhou, Hubei,
China(zzyan@yangtzeu.edu.cn, franklxj001@163.com and xin3fei@21cn.com).}}
\date{}
\maketitle

\begin{abstract} It is well known that the most challenging question in optimization and discrete geometry is whether there is a strongly polynomial time simplex algorithm for linear programming (LP) problems. This paper gives a positive answer to this question by using the parameter analysis technique. We show that there is a simplex algorithm whose number of pivoting steps does not exceed the number of variables of a LP problem.

\textbf{Keywords:} Linear programming, parametric linear programming, complement slackness property, projection polyhedron, simplex algorithm, pivot rule, polynomial complexity \\

\textbf{AMS subject classifications. } 90C05, 90C49, 90C60, 68Q25, 68W40
\end{abstract}

\section{Introduction}
Linear programming (LP) is the problem of minimizing a linear objective function over a polyhedron $P\subset\mathbb{R}^n$ given by a system of $m$ equalities and $n$ nonnegative variables. As Chakraborty et al. \cite{CTA20} recently put it,

{\it "The story of LP is one with all the elements of a grand historical drama. The original idea of testing if a polyhedron is non-empty by using a variable elimination to project down one dimension at a time until a tautology emerges dates back to a paper by Fourier \cite{Fou26} in 1823. This gets re-invented in the 1930s by Motzkin \cite{Mot36}. The real interest in LP happens during World War II when mathematicians ponder best ways of utilising resources at a time when they are constrained". }

\noindent As one of the fundamental problems in optimization and discrete geometry, it has been a very successful undertaking in the field of polyhedral combinatorics in the last six decades. Part of this success relies on a very rich interplay between geometric and algebraic properties of the faces of such a polyhedron and corresponding combinatorial structures of the problem it encodes.

The simplex algorithm, invented by Dantzig \cite{Dan47} solves LP problems by using pivot rules and procedures an optimal solution. Subsequently developed various simplex algorithms are to iteratively improve the current feasible solutions by moving from one vertex of the polyhedron to an adjoint one according to some pivot rule, until no more improvement is possible and optimality is proven. All edges that connect these adjoint vertices of the polyhedron form a pivot path. The complexity of the simplex algorithm is then determined by the length of the path - the number of pivot steps.

The simplex algorithm belongs to the '10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century', see \cite{DS00}. The survey by Terlaky and Zhang \cite{TZ93} contributes the various pivot rules of the simplex algorithm and its variants, in which they categorized pivot rules into three types. The first alternative, which is called combinatorial pivot rule, is to take care of the sign of the variables, including either costs or profits. The algorithms of this type known to the authors are that of Bland \cite{Bla77}, Folkman and Lawrence \cite{FL78}, Fukuda \cite{Fuk82} and etc. The second alternative, which is called parametric pivot rule, is closely related to parametric programming, more precisely to the shadow vertex algorithm \cite{Boy92,Gol83,Mur80} and to Dantig's self-dual parametric simplex algorithm \cite{Dan63}. The algorithms can be interpreted as Lemke's algorithm \cite{Lem65} for the corresponding linear complementarity problem \cite{Lus87}. Algorithms of this third type, which are close connections to certain interior point methods (see Karmarker \cite{Kar84}), allow the iterative points to go inside the polytope. It is believed to be able to use more global information and therefore to avoid myopiness of the simplex method, for example, see Roos \cite{Roo86}, Todd \cite{Tod90} and Tamura et al. \cite{TTF88}.

It is a theoretically interesting and practically relevant question to recognize how a pivot rule \cite{Sha87} quickly leads to the optimal vertex. Connected to this are the diameter problem and the algorithm problem, for example, see \cite{GHZ98}.  Closely to the Hirsch conjecture and its variants,  the diameter problem is whether there a short path to the optimal vertices. Unfortunately Santos' recent counter-example \cite{San12} disproves this conjecture. On the subject for more information see the papers \cite{Bor87,GK93,Mef87,Mir12} and the comments \cite{Eis13,HU13,Lam13,San13,Ter13}. The algorithm problem is whether there is a very strongly polynomial time algorithm for LP. There has been recent interest in finding an algorithm like this for the deterministic Markov decision processes \cite{PY13}, the generalized circulation problem \cite{GJL02}, the maximum flow problem \cite{AW98,GC97}, the minimum cost network flow problem \cite{AW97},  the Arrow-Debreu Market Equilibrium \cite{Jai07} and so on. However, up to now, no pivoting rule yields such a algorithm depending only on the polynomiality of the number of constraints and the number of variables in general, for example, see \cite{Ter13}. In contrast to the excellent practical performance of the simplex algorithm, the worst-case time complexity of each analyzed pivot rule in the field of LP is known to grow exponentially, for example, see \cite{AC78,Gol83,Gol79,KL72,MPZ01,Mur76,Mur80,Pap89,Roo90}. Other exponential example was presented by Fukuda and Namiki \cite{FN94} for linear complementarity problems.

The simplex algorithm has performed sufficiently well in practice, but theoretically the complexity of a pivot rule has so far been quite a mystery. To explain the large gap between practical experience and the disappointing worstcase, the tools of average case analysis and smoothed analysis have been devised, and to conquer the worst case bounds, research has turned to randomized pivot rules. For the average case analysis, a polynomial upper bounded was achieved \cite{Bor87}. In contrast, so far, smoothed analysis has only been done for the shadow-vertex pivot rule introduced by Gaas and Saaty \cite{GS55}. Under reasonable probabilistic assumptions its expected number of pivot steps is polynomial \cite{Spi01}. It is worth noting that none of the existing results exclude the possibility of (randomized) pivot rules being the desired (expected) polynomial-time pivot rules. For more information on the randomized pivot rules reference the papers \cite{EV17,GV07,GHZ98,Kal92,MSW,Mur80,Ver09} and etc.

Two important advances have been made in polynomial time solvability for the ellipsoid method developed by Khachain \cite{Kha80} and the interior-point method initiated by Karmarkar \cite{Kar84} since the 1970s. However, the run time¡¯s complexity of such two algorithms is only qualified as weak polynomial. Actually, constructing a strongly polynomial time pivot rule is the most challenging open question in optimization and discrete geometry \cite{GK93,Mef87,Sma00,Tod00}.

Our main goal of this paper is to give a positive answer to the above open question by the use of the parametric analysis technique that we recently proposed in \cite{YLG20}. We show that there exists a simplex algorithm whose number of pivoting steps does not exceed the number of variables of a LP problem.

The organization of the rest of the paper is as follows. In Section 2, we recall the strong duality theorem of LP. In Section 3, we review the main results of the paper \cite{YLG20}: we define the set-valued mappings between two projection polyhedrons for parametric LP problems and establish the relationship between perturbing the objective function data (OFD) and perturbing the right-hand side (RHS) for a LP problem without using dual. We then investigate the projected behavior of the set-valued mappings in Section 4. As a application, we present the existence of a strongly polynomial time pivot rule for a LP problem in the final section.

\section{Preliminaries} \label{sect21}
Consider the following linear programming (LP) problem pair in the standard forms:
\begin{equation} \label{primaljihe10p} \begin{array}{ll} \min & \langle c, x \rangle \\ s. t. & Ax=b,\\ & x \geq 0 \end{array} \end{equation} and
\begin{equation} \label{primaljihe10d} \begin{array}{ll} \max & \langle b, w \rangle \\ s. t. & A^Tw+y=c,\\ & y \geq 0, \end{array} \end{equation} where $c\in\mathbb{R}^n, b\in\mathbb{R}^m$ and $A\in\mathbb{R}^{m\times n}$ are given. As usual, the first LP problem (\ref{primaljihe10p}) is called the primal problem and the second problem (\ref{primaljihe10d}) is called the dual problem, and the vectors $c$ and $b$ are called the cost and the profit vectors, respectively. By $P=\{x\in\mathbb{R}^n| Ax=b, x\geq 0\}$ and $D=\{(w,y)\in\mathbb{R}^m\times \mathbb{R}^n| A^Tw+y=c, y\geq0 \}$, we denote the feasible sets of the primal and dual problems, respectively.

If the problems (\ref{primaljihe10p}) and (\ref{primaljihe10d}) are feasible and if $b=Ad$, then
\[ \langle d, c-y \rangle = \langle d, A^Tw \rangle = \langle Ad, w \rangle = \langle b, w \rangle. \] Therefore, the dual problem (\ref{primaljihe10d}) can be equivalently expressed as the form \begin{equation} \label{primaljihe10dfg} \begin{array}{ll} \max & \langle d, c-y \rangle \\ s. t. & A^Tw+y=c,\\ & y \geq 0. \end{array} \end{equation}
In following statement, we always use the problem (\ref{primaljihe10dfg}) instead of the dual problem (\ref{primaljihe10d}).

The strong duality theorem provides a sufficient and necessary condition for optimality, for example, see \cite{Dan47,GT56,Mur76,Sch86}.

\thm \label{weakd2} {\bf (Strong duality)} If the primal-dual problem pair (\ref{primaljihe10p}) and (\ref{primaljihe10dfg}) are feasible, then the two problems are solvable and share the same objective value. \upshape

If the primal and dual programs have optimal solutions and the duality gap is zero, then the Karush-Kuhn-Tucker (KKT) conditions for the primal-dual LP problem (\ref{primaljihe10p}) and (\ref{primaljihe10dfg}) pair are
\begin{subequations}
\begin{align} \label{jbkkt1} & Ax = b, \quad x\geq 0, \\ \label{jbkkt2} & A^Tw+y=c, \quad y \geq 0, \\ \label{jbkkt3} & \langle x,y \rangle=0,
\end{align}
\end{subequations} in which the last equality is called the complement slackness property. Conversely, if $(x^*,y^*)\in\mathbb{R}^n\times \mathbb{R}^n$ is a pair of solutions of the system (\ref{jbkkt1})-(\ref{jbkkt3}), then $(x^*,y^*)$ is a pair of optimal solutions of the primal-dual problem pair (\ref{primaljihe10p}) and (\ref{primaljihe10dfg}).

The feasible region of a LP problem is a polyhedron. In particular, a polyhedron is called a polytope if it is bounded. A nontrivial face $F$ of a polyhedron is the intersection of the polyhedron with a supporting hyperplane, in which $F$ itself is a polyhedron of some lower dimension. If the dimension of $F$ is $k$ we call $F$ a $k$-face of the polyhedron. The empty set and the polyhedron itself are regarded as trivial faces. $0$-faces of the polyhedron are called vertices and $1$-faces are called edges. Two different vertices $x^1$ and $x^2$ are neighbors if $x^1$ and $x^2$ are the endpoints of an edge of the polyhedron. For material on convex polyhedron and for many references see Ziegler's book \cite{Zie95}.

\section{Parametric KKT conditions}
Describing a pivot path of the simplex algorithm is a difficult task. The ingredient in our construction is to investigate the relationship between two projection polyhedrons associated with a pair of almost primal-dual problems. Once the relationship is available, either the OFD or the RHS perturbations of the primal and the dual problems are closely linked. The concepts and results in this section come all from the paper \cite{YLG20}.

Consider the following two parametric LP problems with two independent parametric vectors $u,v \in \mathbb{R}^r$
\begin{equation} \label{primaljihe1} \begin{array}{ll} \min & \langle c+M^Tu,x \rangle \\ s. t. & Ax=b,\\ & x \geq 0, \end{array} \end{equation} and
\begin{equation} \label{primaljihe2} \begin{array}{ll} \min & \langle d+M^Tv,y \rangle \\ s. t. & By=a,\\ & y \geq 0, \end{array} \end{equation}
where $A\in\mathbb{R}^{m\times n}, M \in\mathbb{R}^{r\times n}, B\in\mathbb{R}^{l\times n}$, $c,d\in \mathbb{R}^n$, $b\in \mathbb{R}^m$ and $a\in \mathbb{R}^l$.
The following technical claims are assumed to hold throughout this paper.

{\bf Assumption 1}. Three range spaces $R(A^T),R(B^T),R(M^T)$ are orthogonal to each other, and their direct sum is equal to $R^n$.

{\bf Assumption 2}. $MM^T=I_r$, a $r\times r$ unit matrix.

Assumption 1 ensures that the perturbation of the objective function is independent of the constraints in problems (\ref{primaljihe1}) and (\ref{primaljihe2}). A detailed explanation for the assumption can be found in the paper \cite{YLG20}.

For the parametric LP problems (\ref{primaljihe1}) and (\ref{primaljihe2}), their dual problems can be expressed as follow
 \begin{equation} \label{primaljihe1dual} \begin{array}{ll} \max & \langle d, c+M^Tu-y \rangle \\ s. t. & -A^Tw^2+y=c+M^Tu,\\ & y \geq 0 \end{array} \end{equation}
and \begin{equation} \label{primaljihe2dual} \begin{array}{ll} \max & \langle c, d+M^Tv-x \rangle \\ s. t. & -B^Tw^1+x=d+M^Tv,\\ & x \geq 0 \end{array} \end{equation} respectively. If the objective functions in problems (\ref{primaljihe1dual}) and (\ref{primaljihe2dual}) are replaced by $-d^Ty$ and $-c^Tx$, respectively, then their optimal solutions remain unchanged. So the perturbations in (\ref{primaljihe1dual}) and (\ref{primaljihe2dual}) occur in the RHS and not in the OFD.

In the following statements, we always assume that $b=Ad$ and $a=Bc$. In particular, if $(d,c)\geq 0$, then $d$ and $ c$ are feasible solutions of the problems (\ref{primaljihe1}) and (\ref{primaljihe2}), respectively.

If Assumptions 1 and 2 holds, then the problem (\ref{primaljihe2dual}) is equivalent to the problem
\begin{equation} \label{primaljihe4} \begin{array}{ll} \min & \langle c, x \rangle \\ s. t. & Ax=b,\\ & Mx=Md+v, \\ & x \geq 0. \end{array} \end{equation} That is, these two problems have the same optimal solution. Indeed, left multiplying both sides of the equation constraint of (\ref{primaljihe2dual}) by $A$ and $M$, one has $Ax=b$ and $Mx=Md+v$. On the other hand, the system of linear equations $Ax=b$ and $Mx=Md+v$ has a special solution $d+M^Tv$, and the corresponding system of homogeneous equations has a general solution $Bw^1$. In other words, this system has solutions $x=d+M^Tv+B^Tw^1$, which leads to the equality constraint of (\ref{primaljihe2dual}).

Basing on the same reason, the condition (\ref{jbkkt2}) can be replaced by
\begin{equation} \label{jbkkt21} By=a,\quad My=Md,\quad y\geq 0. \end{equation} Analogously, the problem (\ref{primaljihe1dual}) is equivalent to the problem
\begin{equation} \label{primaljihe3} \begin{array}{ll} \min & \langle d,y \rangle \\ s. t. & By=a,\\ & My=Mc+u, \\ & y \geq 0. \end{array} \end{equation}
The LP problems and their interrelationships involved in this paper are shown in Figure \ref{fig:1}.

\begin{figure} \centering \includegraphics[height=10cm,width=9cm]{jiegoutu.png} \caption{Perturbations} \label{fig:1} \end{figure}

Let us define two projection polyhedrons associated with the feasible regions of the problems (\ref{primaljihe3}) and (\ref{primaljihe4}) as follow
\begin{eqnarray*} \varTheta_P &=& \{v\in\mathbb{R}^r| Ax=b, Mx=Md+v, x\geq 0\}, \\
\varTheta_D &=& \{u\in\mathbb{R}^r| By=a, My=Mc+u, y\geq 0\}, \end{eqnarray*} in which $\varTheta_P$ is called {\it a primal projection polyhedron}, and $\varTheta_D$ is called {\it a dual projection polyhedron}. The following result shows that the sets $\varTheta_P$ and $\varTheta_D$ are the projections of the polyhedrons $\{(v,w^1)\in\mathbb{R}^{r+l}| d+M^Tv+B^Tw^1\geq 0\}$ and $\{(u,w^2)\in\mathbb{R}^{r+m}| c+M^Tu+A^Tw^2\geq 0\}$, respectively.

\cor\label{xinzd1} Suppose that $(d,c)\geq 0$.

(1) There is a vector $w^1\in\mathbb{R}^l$ such that the primal slack vector \[x=d+M^Tv+B^Tw^1\] is feasible for the problem (\ref{primaljihe4}) if and only if $v\in \varTheta_P$;

(2) There is a vector $w^2\in\mathbb{R}^m$ such that the dual slack vector \[y=c+M^Tu+A^Tw^2\] is feasible for the problem (\ref{primaljihe3}) if and only if $u\in \varTheta_D$. \upshape

\prof These results follow from Assumptions 1 and 2. $\square$

The problems (\ref{primaljihe1}) and (\ref{primaljihe4}) represent two different perturbations of the problem (\ref{primaljihe10p}). The perturbations in the two problems occur in the OFD and in the RHS, respectively. To characterize the relationship, let us define one set-valued mapping as follow
\[ \Phi(u)= \{ M(x^*(u)-d)| x^*(u) \ \operatorname{is \ an \ optimal \ solution\ of}\ (\ref{primaljihe1})\ \operatorname{if \ it \ exists} \}\] for any $u\in\varTheta_D$. Analogously, we may define another set-valued mapping as follow
\[ \Psi(v)= \{ M(y^*(v)-c)| y^*(v) \ \operatorname{is \ an \ optimal \ solution\ of}\ (\ref{primaljihe2})\ \operatorname{if \ it \ exists} \} \]
for any $v\in\varTheta_P$. Here the value of the mapping $\Phi(u)$ (or $\Psi(v)$) could be a set if the optimal solution is not unique corresponding to the parameter $u$ (or $v$). The similar idea was used by Borrelli et al. \cite{BBM01}.

The set-valued mappings $\Phi$ closely links two different kinds of perturbations of (\ref{primaljihe10p}). Geometrical, the OFD perturbation means that the hyperplane $H=\{x\in \mathbb{R}^n| \langle c+M^Tu,x\rangle=\langle c+M^Tu,x^*(u)\rangle\}$ passing through $x^*(u)$ supports the feasible region $P=\{x\in\mathbb{R}^n|Ax=b,x\geq 0\}$, and the RHS perturbation means that the affine set $C=\{x\in\mathbb{R}^n| Mx=Md+v\}$ cuts the region $P$, in which the affine set $C$ passes through $x^*(u)$ if $v\in\Phi(u)$. A similar geometric explanation applies the set-valued mappings $\Psi$.

\thm\label{maithm1} Suppose that $(d,c)\geq 0$.

(1) For every $u\in \varTheta_D$, $\Phi(u)$ is well defined such that $\Phi(u) \subset \varTheta_P; $

(2) For every $v\in \varTheta_P$, $\Psi(v)$ is well defined such that $ \Psi(v) \subset \varTheta_D. $ \upshape

\prof We only prove the first result. By Theorem \ref{weakd2}, for every $u\in \varTheta_D$, the problem (\ref{primaljihe1}) is solvable that $\Phi(u)$ is well defined. If $x^*(u)$ is an optimal solution of the problem (\ref{primaljihe1}) and if $v\in\Phi(u)$, then $x^*(u)$ is also an optimal solution of the problem (\ref{primaljihe4}). Then by Corollary \ref{xinzd1}, one has $\Phi(u) \subset \varTheta_P$. $\square$

The set-valued mappings defined above play an important role in the development of strong duality theory and in the sensitivity analysis of conic linear optimization. As noted in the paper \cite{YLG20}, either the problem pair (\ref{primaljihe4}) and (\ref{primaljihe3}) or the problem pair (\ref{primaljihe1}) and (\ref{primaljihe2}) is almost dual under the set-valued mappings. The corresponding parametric KKT conditions are provided below.

\thm \label{interior2yy} Let $u\in \varTheta_D$ and $v\in\varTheta_P$ be arbitrary. Then there are a pair of vectors $(\bar{x},\bar{y})\in\mathbb{R}^n \times \mathbb{R}^n$ such that the parametric KKT conditions hold \begin{subequations}
\begin{align}\label{kktcond1} &A \bar{x} = Ad,\quad M \bar{x} =Md+v, \quad \bar{x}\geq 0, \\ \label{kktcond2} &
B\bar{y} = Bc,\quad M\bar{y} =Mc+u, \quad \bar{y}\geq 0,\\ \label{kktcond3} & \langle \bar{x},\bar{y} \rangle=0,
\end{align}
\end{subequations} if and only if both $v\in\Phi(u)$ and $u\in \Psi(v)$ hold. Furthermore, $(\bar{x},\bar{y})$ is a pair of optimal solutions of the almost primal-dual program pair (\ref{primaljihe4}) and (\ref{primaljihe3}) or (\ref{primaljihe1}) and (\ref{primaljihe2}). \upshape

\prof We first show that if the parametric KKT conditions (\ref{kktcond1})-(\ref{kktcond3}) hold, then both $v\in\Phi(u)$ and $u\in \Psi(v)$ hold. Clearly, the above parametric KKT conditions imply that \begin{equation} \label{addtj1} M\bar{y} =Mc+u\end{equation} and \begin{eqnarray*} &A \bar{x}=b,\quad M \bar{x} =Md+v, \quad \bar{x} \geq 0, \\ & B\bar{y} = a, \quad \bar{y} \geq 0,\\ & \langle \bar{x},\bar{y} \rangle=0. \end{eqnarray*} From the KKT conditions (\ref{jbkkt1})-(\ref{jbkkt3}), the second system implies that $(\bar{x},\bar{y})$ is a pair of optimal solutions of the primal-dual program pair (\ref{primaljihe4}) and (\ref{primaljihe2}). Finally, the equality (\ref{addtj1}) implies that $u=M(\bar{y}-c)\in\Psi(v)$. Analogously, one has $v\in\Phi(u)$.

The converse is easy to prove. If both $v\in\Phi(u)$ and $u\in \Psi(v)$ hold, then $\Phi(u)$ and $\Psi(v)$ are well defined, which means the problems (\ref{primaljihe1}) and (\ref{primaljihe2}) have the optimal solution pair $(x^*(u),y^*(v))$. Moreover, $(x^*(u),y^*(v))$ is also a pair of optimal solutions of the problems (\ref{primaljihe4}) and (\ref{primaljihe3}). Then, applying the KKT conditions (\ref{jbkkt1})-(\ref{jbkkt3}) to the primal-dual program pair (\ref{primaljihe1}) and (\ref{primaljihe3}) or (\ref{primaljihe4}) and (\ref{primaljihe2}), $(\bar{x},\bar{y})=(x^*(u),y^*(v))$ satisfies the parametric KKT conditions (\ref{kktcond1})-(\ref{kktcond3}).

The final claim follows from the KKT conditions (\ref{jbkkt1})-(\ref{jbkkt3}) trivially. $\square$

\thm \label{xinzd4} Suppose that $(d,c)\geq 0$. Then \begin{subequations} \begin{align} \label{jihexd1} \bigcup\limits_{u\in \varTheta_D} \Phi(u)= \varTheta_P,\\ \label{jihexd2} \bigcup\limits_{v\in \varTheta_P} \Psi(v) = \varTheta_D.
\end{align}
\end{subequations} \upshape

\prof By Theorem \ref{maithm1}, we have
\begin{equation} \label{nbhgx1} \bigcup\limits_{u\in \varTheta_D} \Phi(u)\subset \varTheta_P. \end{equation} Following we prove that the inverse inclusion relation is true.

Note that the feasible region of of the problem (\ref{primaljihe2}) does not depend on the given parametric vector $v$. Let us number all feasible bases of the problem (\ref{primaljihe2}) and let $\mathcal{I}$ denotes an index set
\[ \mathcal{I} =\{i| y^i\ \operatorname{is \ a \ feasible\ basis\ of\ the \ dual\ problem}\ (\ref{primaljihe2})\}. \]
Then for every $i\in\mathcal{I}$, $y^i$ is a dual feasible basis and $x^i(v)$ is the corresponding dual cost (primal basis, perhaps $x^i(v)$ is primal infeasible for some $v\in \mathbb{R}^r$) such that the complementary condition holds, i. e., $\langle x^i(v),y^i\rangle=0$. Defined the set
\[\varTheta_i=\{v\in\mathbb{R}^r| x^i(v)\geq 0 \}. \] Clearly, one has $\varTheta_i\subset \varTheta_P$ and $\bigcup\limits_{i\in \mathcal{I}}\varTheta_i=\varTheta_P$. If $\varTheta_i$ is not empty, then for every $v\in\varTheta_i$, $x^i(v)$ is feasible and is also optimal for the problem (\ref{primaljihe4}). Therefore, the set $F_i=\{x^i(v)|v\in\varTheta_i\}$ is a nontrivial face of the feasible region of the primal problem (\ref{primaljihe4}); and $y^i$ is also optimal for the problem (\ref{primaljihe3}) corresponding to the parameter $u=u^i=My^i-Mc$. Furthermore, by Theorem \ref{interior2yy}, one has $\Phi(u^i)=\varTheta_i$ such that the inverse of the inclusion relation (\ref{nbhgx1}) holds. $\square$

\cor \label{adjhi} Suppose that $(d,c)\geq 0$, and let $u\in \varTheta_D$. Then $v\in\Phi(u)$ if and only if $u\in\Psi(v)$. \upshape

\prof Assume that $v\in\Phi(u)$. By Theorem \ref{xinzd4}, one has $v\in \varTheta_P$. Then the problems (\ref{primaljihe1}) and (\ref{primaljihe3}) are solvable, and the problem (\ref{primaljihe4}) is also solvable (see \cite[Corollary 3. 3]{YLG20}). Furthermore, the problem (\ref{primaljihe2}) is solvable and $u\in\Psi(v)$. And vice versa. $\square$

\section{The projection transformation}
Consider the almost primal-dual parametric LP problem pair
\begin{equation} \label{primaljihe10c} \begin{array}{ll} \min & \langle c+M^TSu,x \rangle \\ s. t. & Ax=b,\\ & x \geq 0 \end{array} \end{equation} and
\begin{equation} \label{primaljihe10cd} \begin{array}{ll} \min & \langle d+M^TSv, y \rangle \\ s. t. & By=a,\\ & y \geq 0, \end{array} \end{equation}
 where $S\in\mathbb{R}^{r\times r}$ is a symmetric projection matrix, i. e., $S^T=S=S^2$. Such a almost parametric primal-dual LP pair denote the projection of the parametric primal-dual LP pair (\ref{primaljihe1}) and (\ref{primaljihe2}). In particular, if $S$ is an identity matrix, the above two problems become the problems (\ref{primaljihe1}) and (\ref{primaljihe2}), respectively.

Similarly, the following mpCLO problems
\begin{equation} \label{primaljihe40c} \begin{array}{ll} \min & \langle c, x \rangle \\ s. t. & Ax=b,\\ & SMx=SMd+ Sv, \\ & x \geq 0 \end{array} \end{equation}
and \begin{equation} \label{primaljihe20c} \begin{array}{ll} \min & \langle d,y \rangle \\ s. t. & By=a,\\ &S My = SMc+Su, \\ & y \geq 0 \end{array} \end{equation} are the Lagrangian duals of problems (\ref{primaljihe10c}) and (\ref{primaljihe20c}), respectively. Then the corresponding mpKKT property is as follows
\begin{subequations}
\begin{align}\label{skktcond1} &A x =b,\quad Mx= Md + Sv,\quad x\geq0 , \\ \label{skktcond2} &
By = a,\quad My= Mc+Su,\quad y\geq0,\\ \label{skktcond3}& \langle x,y \rangle=0.
\end{align}
\end{subequations}

\thm\label{mfzjia1} Let $(d,c)\geq0$, and let $S\in\mathbb{R}^{r\times r}$ be a symmetric projection matrix.

(1) For every $u\in \varTheta_D$, there exists a vector $v\in S\varTheta_P$ such that $Sv\in\Phi(Su)$ and $Su\in\Psi(Sv)$;

(2) For every $v\in \varTheta_P$, there exists a vector $u\in S\varTheta_D$ such that $Su\in\Psi(Sv)$ and $Sv\in\Phi(Su)$. \upshape

\prof Clearly, if $v\in S\varTheta_P(d)$ or $u\in S\varTheta_D(c)$, then $Sv=v$ or $Su=u$. Then the result follows from Theorem \ref{maithm1} and Corollary \ref{adjhi}. $\square$

\section{Polynomial complexity}
Prior to the study of sensitivity analysis in recent years, the actual invariancy region plays an important role in the development of parametric LP. Adler and Monteiro \cite{AM92} investigated the sensitivity analysis of LP problems first using the optimal partition approach, in which they identify the range of parameters where the optimal partition remains invariant. Other treatments of parametric analysis for LP problems based on the optimal partition approach was given by Jansen et al. \cite{JR03}, Greenberg \cite{Gre94}, and Roos et al. \cite{RTV05}, Ghaffari-Hadigheh et al. \cite{GG08}, Berkelaar et al. \cite{Ber97}, Dehghan et al. \cite{Deh07}, Hlad$\acute{i}$k \cite{Ha10} and etc.

\defn \label{djkyi1} Let $\mathcal{V}$ be a simply connected subset of $\varTheta_P$. Then $\mathcal{V}$ is called an invariancy set if for all $v^1,v^2\in\mathcal{V}$, one of the following statements holds:

 (1) $\Psi(v^1)=\Psi(v^2)$ if $\mathcal{V}$ is not a singleton set;

 (2) $\Psi(v^1)$ is not a singleton set if $\mathcal{V}$ is equal to $\{v^1\}$.

In the approach one can identify the range of parameters where the optimal partition invariant. In this definition, the first claim means that the dual optimal objective value remains unchange, whereas the second claim means that the primal optimal objective value remains unchange.

The notation $\operatorname{dim}(\mathcal{V})$ denotes the dimension of the affine hull of the set $\mathcal{V}$.

\defn Let $\mathcal{V}$ be an invariancy set of $\varTheta_P$. Then $\mathcal{V}$ is called a transition face if $\operatorname{dim}(\mathcal{V})<r$. In particular, if $\operatorname{dim}(\mathcal{V})=0$, then $\mathcal{V}$ is called a transition point; and if $\operatorname{dim}(\mathcal{V})=1$, then $\mathcal{V}$ is called a transition line, and etc. \upshape

For the dual projection polyhedron $\varTheta_D$, the definitions of the invariant set and the transition face is similar.

We refer to an invariancy set as a nontrivial invariancy set if it is not a transition face. In contrast, a transition face is called a trivial invariancy set.

\thm \label{zyjg1} Any two different invariancy regions of a projection polyhedron do not intersect. \upshape

\prof This result follows immediately from Definition \ref{djkyi1}. $\square$

Following we focus on single-parameter LP problems. For this type of the parametric LP problems, a nontrivial invariancy set is a open interval. Moreover, the endpoints of invariancy interval are the transition points (see also \cite{RTV05}).

\thm \label{AMyiny2} Suppose that $(d,c)\geq 0$, and let $r=1$.

(1) If $u\in\varTheta_D$ is given, then $\Phi(u)=[\underline{v},\overline{v}]$ can be identified by solving the following two auxiliary LP problems:
\begin{eqnarray*} \underline{v} &=& \min\{v| \operatorname{\exists \ (\bar{x},\bar{y})\ s. t. \ the\ parametric\ KKT\ conditions} \ (\ref{kktcond1})-(\ref{kktcond3})\ \operatorname{holds}\},\\ \overline{v}&=& \max \{v| \operatorname{\exists \ (\bar{x},\bar{y})\ s. t. \ the\ parametric\ KKT\ conditions} \ (\ref{kktcond1})-(\ref{kktcond3})\ \operatorname{holds}\}. \end{eqnarray*}

(2) If $v\in\varTheta_P$ is given, then $\Psi(v)=[\underline{u},\overline{u}]$ can be identified by solving the following two auxiliary LP problems:
\begin{eqnarray*} \underline{u} &=& \min\{u| \operatorname{\exists \ (\bar{x},\bar{y})\ s. t. \ the\ parametric\ KKT\ conditions}\ (\ref{kktcond1})-(\ref{kktcond3})\ \operatorname{holds}\},\\ \overline{u}&=& \max \{u | \operatorname{\exists \ (\bar{x},\bar{y})\ s. t. \ the\ parametric\ KKT\ conditions} \ (\ref{kktcond1})-(\ref{kktcond3})\ \operatorname{holds}\}. \end{eqnarray*} \upshape
\indent \prof The result follows from Theorem \ref{interior2yy}. $\square$

The open interval $(\underline{v},\overline{v})$ is an invariancy interval, and the finite endpoints of the invariancy interval are transition points. Of course, either $\underline{v}=-\infty$ or $\overline{v}=+\infty$ is allowed. The similar results apply the set-valued mapping $\Psi$. Two direct consequences of Theorem \ref{AMyiny2} is as follows.

\cor \label{AMyiny3} Suppose that $(d,c)\geq 0$, and let $r=1$.

(1) If $\Phi(u)=[\underline{v},\overline{v}]$ is an interval, where $\underline{v}\ne\overline{v}$, then all optimal solutions $\bar{x}^*(v)$ of the problem (\ref{primaljihe4}) for $v\in [\underline{v},\overline{v}]$ forms an edge of the primal feasible region of $P=\{x\in\mathbb{R}^n| Ax=b,x\geq 0\}$, in which $\bar{x}^*(\underline{v})$ and $\bar{x}^*(\overline{v})$ are two adjoint vertices of $P$ if $\underline{v}$ and $\overline{v}$ are finite. And the optimal solutions of the dual problems (\ref{primaljihe2}) and (\ref{primaljihe3}) remain unchange.

(2) If $\Psi(v)=[\underline{u},\overline{u}]$ is an interval, where $\underline{u}\ne\overline{u}$, then all optimal solutions $\bar{y}^*(u)$ of the problem (\ref{primaljihe3}) for $u\in [\underline{u},\overline{u}]$ forms an edge of the dual feasible region of $D=\{y\in\mathbb{R}^n| By=a,y\geq 0\}$, in which $\bar{y}^*(\underline{u})$ and $\bar{y}^*(\overline{u})$ are two adjoint vertices of $P$ if $\underline{u}$ and $\overline{u}$ are finite. And the optimal solutions of the primal problems (\ref{primaljihe1}) and (\ref{primaljihe4}) remain unchange.
\upshape

\cor \label{AMyiny4} Suppose that $(d,c)\geq 0$, and let $r=1$.

(1) If $\Phi(u)=[\underline{v},\overline{v}]$ is an interval, where $\underline{v}\ne\overline{v}$, then for any $v\in (\underline{v},\overline{v})$, $\Psi(v)=u$.

(1) If $\Psi(v)=[\underline{u},\overline{u}]$ is an interval, where $\underline{u}\ne\overline{u}$, then for any $u\in (\underline{u},\overline{u})$, $\Phi(u)=v$. \upshape

From Corollary \ref{AMyiny3} , a projection interval ($\varTheta_P$ or $\varTheta_D$) is the union of finite open invariancy intervals and transition points, see also Adler and Monterio \cite{AM92}. For the primal projection interval $\varTheta_P$, there is a finite set of transition points $v_1<v_2<\dotsc<v_k$ such that
\[\varTheta_P=\bigcup\limits_{i=1}^{k-1}[v_i,v_{i+1}], \] in which every open interval $(v_i,v_{i+1})$ is an invariancy interval, and $v_1=-\infty$ and/or $v_k=+\infty$ are allowed. Then by Corollary \ref{AMyiny4}, for the dual projection interval $\varTheta_D$, there is a finite set of transition points $u_1<u_2<\dotsc<u_{k-1}$ such that $\Psi((v_i,v_{i+1}))=u_i$ for $i=1,2,\cdots,k-1$. And every $\Psi(v_i)$ is a closed interval whose interiors forms an open invariancy interval of $\varTheta_D$ if $v_i$ is finite. In particular, if $v_1$ is finite, then $\Psi(v_1)=[u_{k-1},+\infty)$; and if $v_k$ is finite, then $\Psi(v_k)=(-\infty,u_1]$. All in all, if $\varTheta_P$ contains $k-1$ open invariancy intervals, then $\varTheta_D$ contains $k-2$ to $k$ open invariancy intervals.

\cor \label{finite2} If $l=r=1$, then $\varTheta_P$ contains $n$ transition points and $n$ invariancy intervals at most. \upshape

\prof Since there's only one dual constraint, the parametric LP problem (\ref{primaljihe2}) is easy to be solved by the use of the simplex algorithm. Hence the dual basic variable $y_j$ can be chosen by the ratio test
\[ j\in \mathcal{J}=\left\{j\left| \frac{a}{b_{1j}}>0, b_{1j}\ne 0\right. \right\}. \] Clearly, the number of the entries of the index set $\mathcal{J}$ is less than or equal to $n$. If the number of the index set $\mathcal{J}$ is equal to $n$, then by Corollary \ref{AMyiny3}, $\varTheta_P$ has $n$ finite transition points and $n-1$ invariancy intervals. Otherwise, the number of finite transition points is less than $n$ and the number of invariancy intervals is less than or equal to $n$. $\square$

The main result of this paper is as follows.

\thm\label{mainlp1} If $(d,c)\geq 0$, then there is a pivot rule such that the simplex algorithm solves the problem (\ref{primaljihe10p}) at most in $n$ steps. \upshape

\prof For the given problem (\ref{primaljihe10p}), consider the almost primal-dual problem pair (\ref{primaljihe10c}) and (\ref{primaljihe10cd}) with $r=n-m-1$ and $l=1$, where $S$ is a $r\times r$ symmetric projection matrix of rank 1. By Corollary \ref{finite2}, the set $S\varTheta_P=\{Sv|v\in \varTheta_P\}$ contains $n$ transition points and $n$ invariancy intervals at most. Then by Theorem \ref{mfzjia1}, the set $S\varTheta_D=\{Su|u\in \varTheta_D\}$ contains $n$ transition points and $n$ invariancy intervals at most, which implies the desired result. $\square$


TITLE: prove that a function is expressible as a power series
QUESTION [2 upvotes]: I started by rearrange f(z), and expanded the terms in summation.

Then, I did not get very far. It would be great if anyone can let me know what is needed to figure out bn. Thanks in advance.

REPLY [2 votes]: You were kinda in the right track, I'll leave it as steps so you can prove it yourselv (fill the gaps), its not an easy theorem.
$1)$ Note that (as you already did): $$\sum_{n = 0}^{\infty} a_n z^n = \sum_{n = 0}^{\infty} a_n (z - z_0 + z_0)^n$$
$$= \sum_{n = 0}^{\infty} a_n \sum_{k = 0}^{n} \binom{n}{k} {z_{0}}^{n-k}(z-z_0)^n$$
$$= \sum_{n = 0}^{\infty} a_n \sum_{k = 0}^{\infty} \binom{n}{k} {z_{0}}^{n-k}(z-z_0)^n $$
Here the pass from the second to third equal is trivial because remember what happens to the binomial if $k > n$.
$2)$ If $c_n = a_n \sum_{k = 0}^{\infty} \binom{n}{k} {z_{0}}^{n-k}(z-z_0)^n$ prove that $\sum c_n$ is absolutely convergent. Hint (apply absolute value to $c_n$ and go backwards with the binomial theorem, then apply your hypothesis on the radius of convergence).
$3)$ Write each $c_n$ for each $n = 0,1,\dots$ as an infinite matrix where each $c_n$ is a row.
$4)$ Because we proved the convergence is absolute we can rearrange the series, now every colum is the sum of some value (remember the $a_n$ and $z_0$ are fixed) multiplied by a power of $(z-z_0)$
Concluded that if you sum the colums and then the row that is changing the sums on $$\sum_{n = 0}^{\infty} a_n \sum_{k = 0}^{\infty} \binom{n}{k} {z_{0}}^{n-k}(z-z_0)^n $$
You'll get
$$ \sum_{k = 0}^{\infty} \bigg ( \sum_{n = k}^{\infty} a_n\binom{n}{k} {z_{0}}^{n-k}\bigg)(z-z_0)^n $$
So $b_k =  \sum_{n = k}^{\infty} a_n\binom{n}{k} {z_{0}}^{n-k}$


TITLE: Irreducible unitary representations of locally compact groups
QUESTION [3 upvotes]: Let $G$ be a locally compact group and let $\mu$ be a left Haar measure. We know
that $\mu$ is unique up to a scalar in $\mathbf{R}_{>0}$. I don't know so much about unitary representations of groups but for the sake of convenience let us make the following definition:
Let $(V,\langle\ ,\ \rangle)$ be an Hilbert space over $\mathbf{C}$ of countable (finite or infinite) orthonormal Schauder basis. We let Let $GL_{cont}(V)$ be the set of bounded (with respect to the operator norm) linear operators on $V$. We may view $GL_{cont}(V)$ as a topological group via the discrete topology. Now let $M$ be a $\mathbf{C}$ vector space with a linear $G$-action. We will say that $M$ is a unitary irreducible representation of $G$ if there exists an abstract isomorphism of $\mathbf{C}$ vector spaces $f:M\rightarrow V$ (where $V$ is chosen as above) such that the natural map $GL(M)\rightarrow GL(V)$
(1) factors through $GL_{cont}(V)$
(2) $V$ is irreducible as a $G$-module
(3) For all $g\in G$ and all $v,w\in V$ one has that $\langle\rho(g)v,\rho(g)w\rangle=\langle v,w\rangle$.
Now let us consider the space $L^2(G)$ of all functions
$f:G\rightarrow\mathbf{C}$ where $f$ is measurable and square integrable with respect to the Haar measure. Note that this space has a natural structure of a $G$-module through left action.
Now in the special case where $G$ is a compact Lie group ($G$ is not necessarily connected so in particular this covers all finite groups) then all irreducible representation
are unitary (the average trick) and finite dimensional (this I think is non-trivial and follows from Peter-Weyl, actually I never looked at the proof of this result). Moreover, if
$\widehat{G}$ denote a complete set irreducible $\mathbf{C}$ representations of $G$ (up to isomorphisms as (unitary) $G$-modules) then one has that
$L^2(G)=\bigoplus_{\phi\in\widehat{G}}\oplus_{i,j}\sqrt{n_{\phi}}\phi_{ij}$ where $n_{\phi}=dim(\phi)$ and
$\phi_{ij}$ is the $(i,j)$-th entry of $\phi:G\rightarrow GL(V_{\phi})$. In other words all irreducible unitary representations (say $\phi$ is one of them) of $G$ occur in $L^2(G)$ with multiplicities $n_{\phi}$. The direct sum here should be understood in the sense of Schauder basis with respect to the topology induced by $\langle\ ,\ \rangle$. Note that
$\lbrace\sqrt{n_{\phi}}\phi_{i,j}\rbrace$ gives an orthonormal basis of $L^2(G)$.
Now here is a set of natural questions:
(1) Do all the irreducible unitary representations of a semi-semiple (reductive)
algebraic group over $\mathbf{R}$ occur in $L^2(G)$?
(2) On the other side of the spectrum, what about  algebraic solvable groups?
(3) What is the minimal example of a locally compact topological group $G$ (with an non artificial tailor made topology, in particular $G$ has to be infinite) for which one can find an irreducible unitary representation which does not occur in $L^2(G)$?

REPLY [3 votes]: For (1) and (3), there are plenty of irreducible unitary representations of SL2(R) that do not occur in the regular representation, such as complementary series, limits of discrete series, and for that matter the trivial representation.


TITLE: How $xN · yN = yN · xN$ is equivalent, to $xN · yN · (xN )^{−1} · (yN )^{−1} = N$.
QUESTION [2 upvotes]: How $xN · yN =
yN · xN$ is   equivalent, to
$xN · yN · (xN )^{−1} · (yN )^{−1} = N$.
Where N is normal subgroup.
$EDIT: 1$
$x \in G $, $y \in G$ and $xN$ is coset.

REPLY [4 votes]: Well since $N$ is normal, you are dealing with the elements of the group $G/N$. So, multiplying both sides of $xN · yN · (xN )^{−1} · (yN )^{−1} = N $ on the right with first $yN$ and then $xN$ yields
$$
xN\cdot yN=N\cdot yN\cdot xN
$$
Since $N$ is the identity of that group, the right hand side is just $yN\cdot xN$
The converse follows by just reversing the steps.


TITLE: Find all integer solutions of equation $y = \frac{a+bx}{b-x}$
QUESTION [0 upvotes]: How to find all integer solutions for the equation
$y = \frac{a+bx}{b-x}$, where a and b are known integer values?
P.S. x and y must be integer at the same time

REPLY [2 votes]: First multiply denominator to other side : $0 = yx + bx - by + a = (x-b)(y+b) + a + b^2$
$(x-b)(y+b) = -(a+b^2)$
Then all you need is to write RHS as multiplication of 2 integers: $-(a+b^2) = mn$ and then get 2 solutions $(m+b, n-b)$ and $(n+b, m-b)$ for all different $(m, n)$ pairs.
Corner case:
$a = -b^2$, then all $(x,-b)$ is solution except $x=b$ since function is not defined at $x=b$


TITLE: Short explanation for hamiltonian cycles in $Q_3$
QUESTION [0 upvotes]: The task is to find the count of hamiltonian cycle in $Q_3$.
So I know the answer is $6$, but i don't know why or how to get it.

My first attempt was simple: I start from edge $6$, and I have $3$ $(2,5,8)$, then I have another $2$ (so I will get $3\cdot 2=6)$. But this doesn't help, because by choosing the first two edges of the cycle, we don't get any perticular Hamilton Cycle.
Any tips?

REPLY [1 votes]: You're right that you have six starting choices: 621, 624, 651, 657, 684, 687.
You can extend them further until they form a cycle. Some of the options will form the same cycle. For example, because order doesn't matter, 62157386 is the same Hamiltonian cycle as the reverse 68375126.
Using your procedure, starting from node 6, you have three choices, then two choices, then two choices, then one choice(!) for completing the rest of the Hamiltonian path. So altogether, it seems like there are 3*2*2 = 12 choices. However, we're counting each path twice. We need to consider the reverse of a path to be equivalent to the original path.  When we do, there are actually six Hamiltonian paths altogether.


TITLE: How to prove the laguerre polynomial has n zero point?
QUESTION [2 upvotes]: Here is an equation:
$$
e^x\frac{d^n(x^ne^{-x})}{dx^n}=0
$$
Now I want to prove that this equation has $n$ different roots.
I tried to convert the equation to this form:
$$
\sum\limits_{k=0}^{n}C_n^k(-1)^{n-k}\frac{n!}{k!}x^{n-k}=0
$$
But I don't know how to prove that it has exactly $n$ different roots. So what should I do?
A hint is enough!

REPLY [2 votes]: Rolle's theorem is enough. $f(x)=x^n e^{-x}$ has a root with multiplicity $n$ at the origin and it vanishes at $+\infty$.
$f'(x)$ has a root with multiplicity $n-1$ at the origin, a simple root at some $x_0\in\mathbb{R}^+$ (local maximum for $f$) and it vanishes at $+\infty$. $f''(x)$ has a root with multiplicity $n-2$ at the origin, a simple root somewhere between $0$ and $x_0$ and a simple root somewhere after $x_0$. Use induction and you are done.
The same argument also applies to (shifted) Legendre polynomials, essentially given by $\frac{d^n}{dx^n}\left(x^n(1-x)^n\right)$.
The largest root of a Laguerre polynomial can be estimated using the techniques shown here for Hermite polynomials.


TITLE: Word problems on Sets
QUESTION [2 upvotes]: In an examination, $80$ students passed in maths, $70$ failed in maths, $90$ failed in science and $20$ failes in both subjects.
How many passed in science$?$
How many passed in both subjects$?$

REPLY [2 votes]: Let
$a=|\{$pass math, pass science$\}|$
$b=|\{$pass math, fail science$\}|$
$c=|\{$fail math, pass science$\}|$
$d=|\{$fail math, fail science$\}|$
Then $a+b=80,c+d=70,b+d=90,d=20$
We can easily solve to be $b=70,c=50,a=10$.
Hence pass science $=a+c=60$ and pass both $=a=10$


TITLE: Graph Theory Vertex Problem
QUESTION [3 upvotes]: Let $G$ be a graph of order $8$ with $V(G)=\{v_1, v_2,...,v_8\}$ such that deg $v_i=i$ for $1 \leq i \leq 7$. What is deg $v_8$.
Any help or hints would be greatly appreciated.

REPLY [4 votes]: You must join $v_7$ with all other vertices.
After that, $v_1$ is already "fed up". What can you now say about $v_6$? What happens then to $v_2$? And so on.


TITLE: Proving a determinant equal a 0
QUESTION [0 upvotes]: How can I prove that this type of determinant is equal to zero. I couldn't figure out how to start this test or any counter-test. If p is one, the determinant is null. How to begin?
$
\begin{equation}
A = \begin{bmatrix}
(1 - p)a_1 & a_2 & \dots  & a_n \\
a_1 & (1 - p)a_2 & \dots & a_n  \\
\vdots  & \vdots & \ddots &  \vdots \\
a_1 & a_2 & \dots & (1 - p)a_n \\
\end{bmatrix}
\end{equation}
$

REPLY [0 votes]: The determinant is $(-1)^n a_1 \cdots a_n p^{n-1}(p-n)$ and so is zero iff $a_k=0$ for some $k$ or $p=0$ or $p=n$.
This follows from the matrix determinant lemma, since $A=D+B$ where $D$ is a diagonal matrix and $B$ has rank $1$.


text:
\begin{document}

\title[Twisted (co)homology of ${}_{m+1} F_m$]
{Intersection numbers and twisted period relations
for the generalized hypergeometric function ${}_{m+1} F_m$
}

\author[Y. Goto]
{Yoshiaki Goto}

\address{Department of Mathematics,
Graduate School of Science,
Kobe University,
Kobe 657-8501, Japan}
\email{y-goto@math.kobe-u.ac.jp}

\subjclass[2010]{33C20}
\keywords{generalized hypergeometric functions,
twisted (co)homology group, intersection forms, twisted period relations.}
\dedicatory{}

\maketitle

\begin{abstract}
We study the generalized hypergeometric function ${}_{m+1} F_m$
and the differential equation ${}_{m+1}E_m$ satisfied by it.
We use the twisted (co)homology groups
associated with an integral representation
of Euler type.

We evaluate the intersection numbers of some twisted cocycles
which are defined as $m$-th exterior products of logarithmic $1$-forms.

We also give twisted cycles corresponding to the series solutions
to ${}_{m+1}E_m$,

and evaluate the intersection numbers of them.
These intersection numbers of the twisted (co)cycles lead
twisted period relations which give
relations for two fundamental systems of solutions to ${}_{m+1}E_m$.

\end{abstract}

\section{Introduction}
The generalized hypergeometric function ${}_{m+1} F_m$ of
a variable $x$ with complex parameters
$a_0 ,\ldots ,a_m ,b_1 ,\ldots ,b_m$ is defined by
\begin{align*}
  \gh{m+1}{m} \para{a_0 ,\ldots ,a_m}{b_1 ,\ldots ,b_m}{x}
  =\sum_{n=0} ^{\infty }
  \frac{(a_0,n) \cdots (a_m ,n)}
  {(b_1 ,n)\cdots (b_m ,n) n!} x^n,
\end{align*}
where $b_1 ,\ldots ,b_m \not\in \{ 0,-1,-2,\ldots \}$
and $(c,n)=\Gamma (c+n)/\Gamma (c)$.
This series converges in the unit disk $|x|<1$, and
satisfies the generalized hypergeometric differential equation
\begin{align*}
\GHE =
\GHE \paraE{a_0,\ldots ,a_m}{b_1,\ldots ,b_m}:
\left[
\theta \prod_{i=1}^m (\theta +b_i-1)
-x\prod_{j=0}^m (\theta -a_j)
\right] f(x)=0,
\end{align*}
where $\theta =x \frac{d}{dx}$.
The linear differential equation $\GHE$ is of rank $m+1$
with regular singular points $x=0,1$, and $\infty$.
If $b_i-b_j \not\in \Z \ (0\leq i<j \leq m)$,
a fundamental system of solutions to $\GHE$ around $x=0$
is given by the following $m+1$ functions:
\begin{align}
  \begin{array}{l}
    f_0:=\GH \para{a_1 ,\ldots ,a_{m+1}}{b_1 ,\ldots ,b_m}{x} , \\
    f_{r} :=x^{1-b_r} \cdot
    \GH \para{a_0 -b_r +1 ,\ldots ,a_m-b_r +1}
    {b_1-b_r+1 ,\ldots ,2-b_r ,\ldots ,b_m -b_r+1}{x},
  \end{array}\label{series-sol}
\end{align}
where $1\leq r \leq m$.
It is known that
$\GH$ admits the integral representation of Euler type:
\begin{align}
  & \GH \para{a_0,\ldots ,a_m}{b_1 ,\ldots ,b_m}{x} \label{integral} \\
  & =\prod_{i=1}^{m} \frac{\Ga(b_i)}{\Ga(a_i)\Ga(b_i-a_i)}
  \int _{D }
  \prod_{j=1}^{m-1} \left( t_j ^{a_j -b_{j+1}} (t_j-t_{j+1})^{b_{j+1} -a_{j+1} -1} \right) \nonumber \\
  & \hspace{40mm} \cdot t_m^{a_m -1} (1-t_1)^{b_1-a_1-1} ( 1-x t_m ) ^{-a_0} dt_1 \wedge \cdots \wedge dt_m,
  \nonumber
\end{align}
where
$D :=\{ (t_1 ,\ldots ,t_m) \in \R^m \mid 0<t_m <t_{m-1} <\cdots <t_1<1 \}$.
The branch of the integrand is defined
by the principal value for $x$ near to $0$.

In this paper, we consider the twisted (co)homology groups associated with
the integral representation (\ref{integral}).
Note that the singular locus of the integrand of (\ref{integral}) is not normally crossing.
In such a case, as is studied in \cite{KY}, the resolution of singularities
is an effective way for the study of intersections of the twisted (co)homology groups.
However, our singularities are so complicated for a general $m$ that
it seems difficult to resolute them.
To conquer this difficulty, we find a systematic method completing
the resolution of the singular locus.
We blow up the singular locus step by step and
use the combinatorial structure of divisors which should exist in the complete resolution.
The resolution of the singular locus enables us to evaluate intersection numbers
for twisted cocycles.
We give formulas for the intersection numbers of $m$-th exterior products of
logarithmic $1$-forms, which span the twisted cohomology group.
For the study of the twisted homology group, we avoid the complexity of the resolution.
We construct twisted cycles corresponding to
the $m+1$ solutions (\ref{series-sol}) to $\GHE$
by using the method given in \cite{G-FC} and \cite{G-FA}.
They are made by the bounded chambers, and their boundaries are
canceled by different ways from the usual regularization.
It is an advantage of our construction that we can evaluate their intersection numbers
by the formula in \cite{Y} for a normally crossing singular locus.
Intersection numbers of twisted homology and cohomology groups
imply twisted period relations for two fundamental systems
of solutions to $\GHE$ with different parameters.
These relations are transformed into
quadratic relations among hypergeometric series $\GH$'s.
Since our intersection matrices are diagonal,
it is easy to reduce the twisted period relations to quadratic relations
among $\GH$'s.

In \cite{Mimachi}, twisted cycles corresponding to the solutions (\ref{series-sol})
to $\GHE$ are obtained from real (non-bounded) chambers,
and their intersection numbers are evaluated by the method in \cite{KY}.
Since these cycles are scalar multiples of ours as elements of
the twisted homology group, we give their explicit correspondence in
Remark \ref{cf-Mimachi}.
Twisted period relations for $\GH$ are given in \cite{Ohara}
by the study of the intersection forms of (co)homology groups
with coefficients in the local system of rank $m$
given as the solution space to $\GHE$.
Another integral representation of $\GH$ and
its inductive structure are used in \cite{Ohara}.

As is in \cite{BH}, the irreducibility condition of
the differential equation $\GHE$ is
known to be
$a_i -b_j \not\in \Z \ (0\leq i,j \leq m)$,
where we put $b_0:=0$ (though $b_0$ is usually defined by 1,
we use this setting for our convenience).
Since we use the fundamental system (\ref{series-sol}) of solutions to $\GHE$,

we assume throughout this paper that the parameters $a_i,\ b_j$
satisfy the condition
\begin{align}\label{condition}
  a_i -b_j \not\in \Z  \ (0\leq i,j \leq m),\quad
  b_i -b_j \not\in \Z  \ (0\leq i<j \leq m).
\end{align}

\section{Twisted (co)homology groups
associated with the integral representation (\ref{integral})}\label{section-THG}
For twisted homology groups, twisted cohomology groups,
and the intersection forms,

refer to \cite{AK}, \cite{Y}, or \cite{G-FC}.
We use the same notations as in \cite{G-FC} and \cite{G-FA}.

In this paper, we mainly consider
the twisted (co)homology group in \cite{G-FC} for
$$
M:=\C ^m -\left( \bigcup_{j=1}^m (t_j=0) \cup
\bigcup_{j=2}^m (t_{j-1}-t_j=0) \cup (1-t_1=0) \cup (1-xt_m=0)  \right)
$$
and the multi-valued function
\begin{align*}
  u :=& \prod_{j=1}^m t_j^{a_j-b_{j+1}} \cdot
  \prod_{j=2}^m (t_{j-1}-t_j)^{b_j-a_j} \cdot (1-t_1)^{b_1-a_1} \cdot (1-xt_m)^{-a_0} .
\end{align*}
We put $\om :=d \log u$, where $d$ is the exterior derivative
with respect to the variables $t_1 ,\ldots ,t_m$
(not to $x$ regarded as a parameter).
The twisted cohomology group,
that with compact support, and the twisted homology group
are denoted by $H^k (M,\na_{\om})$, $H_c ^k (M,\na_{\om})$, and
$H_k(\CC_{\bu} (M,u))$, respectively.
Here, $\na_{\om}$ is the covariant differential operator defined as
$\na_{\om} :=d+\om \wedge$.

The expression (\ref{integral}) means that the integral
$$
\int_{D \otimes u} u \vph_0 ,\ \
\vph_0  :=\frac{dt_1 \wedge \cdots \wedge dt_m }
{t_m (1-t_1) (t_1-t_2) \cdots (t_{m-1}-t_m)}
$$
represents $\GH$ modulo Gamma factors.
By \cite{AK} and \cite{Cho}, we have $H^k(M,\na_{\om})=0$ $(k \neq m)$,
$\dim H^m (M,\na_{\om})=m+1$,
and there is a canonical isomorphism
$$
\jmath : H^m (M,\na_{\om}) \to H_c ^m (M,\na_{\om}) .
$$
By the Poincar\'{e} duality, we have
\begin{align*}
  & \dim H_k (\CC_{\bu} (M,u))=\dim H^k(M,\na_{\om})=0 \ \  (k \neq m),\\
  & \dim H_m (\CC_{\bu} (M,u))=\dim H^m(M,\na_{\om})=m+1.
\end{align*}

The intersection form $I_h$ on the twisted homology groups is
the pairing between $H_m (\CC_{\bu} (M,u))$ and $H_m (\CC_{\bu} (M,u^{-1}))$.
The intersection form $I_c$ on the twisted cohomology groups is
the pairing between $H_c^m (M,\na_{\om})$ and $H^m (M,\na_{-\om})$.
By using $\jmath$, we can regard the intersection form $I_c$
as the pairing between $H^m (M,\na_{\om})$ and $H^m (M,\na_{-\om})$, i.e.,
$$
I_c (\psi ,\psi'):=\int_M \jmath (\psi) \wedge \psi' ,\quad
\psi \in H^m(M,\na_{\om}) ,\ \psi' \in H^m (M,\na_{-\om}).
$$

\section{Twisted cohomology groups and intersection numbers}
In this section, we give two systems of twisted cocycles,
and evaluate their intersection numbers.

We embed $M$ into the projective space $\P^m$, that is,
we regard $M$ as the open subset of $\P^m$:
\begin{align*}
  M=\P^m -\left( \bigcup _{j=0}^m L_j \cup \bigcup _{j=0}^m H_j  \right)
  \subset \C^m \subset \P^m ,
\end{align*}
where
\begin{align*}
  & L_j :=(T_j=0) \ (0 \leq j \leq m), \\
  & H_j :=(T_{j-1}-T_j =0) \ (1 \leq j \leq m) ,\ H_0 :=(T_0-xT_m =0).
\end{align*}
By the homogeneous coordinates $T_0 ,\ldots ,T_m$,
the multi-valued function $u$ is expressed as
\begin{align*}
  u=T_0^{\la_0} (T_0 -xT_m)^{\mu_0} \cdot
  \prod_{j=1}^m T_j^{\la_j} (T_{j-1} -T_j)^{\mu_j} ,
\end{align*}
where
\begin{align*}
  & \la _j :=a_j -b_{j+1} \ (1 \leq j \leq m-1) ,\ \la_m :=a_m ,\\
  & \mu _j :=b_j -a_j \ (1 \leq j \leq m) ,\ \mu_0 :=-a_0 ,\\
  & \la_0 :=-\left( \sum_{j=1}^{m} \la_j +\sum_{j=0}^{m} \mu_j \right) =a_0 -b_1.
\end{align*}
Note that $L_0=(T_0 =0)$ is the hyperplane at infinity,
i.e., $M \subset \C^m =\P^m -L_0 \subset \P^m$ and
the coordinates $t_1 ,\ldots ,t_m$ on $\C^m$ are defined as $t_j =T_j /T_0$.
Hereafter, we regard subscripts as elements in $\Z /(m+1)\Z$.
For example, we have $a_{m+1}=a_0$, $b_{m+1}=b_0=0$, and
$$
\la_j =a_j-b_{j+1} ,\ \mu_j =b_j -a_j \quad  (0 \leq j \leq m).
$$

Let $\ell_k$ and $h_k\ (0\leq k \leq m)$ be
the defining linear forms of $L_k$ and $H_k$, respectively.
We define an $m$-form on $M$ by
$$
\phi (f_0,\ldots ,f_m):=
d\log \left( \frac{f_0}{f_1} \right) \wedge
d\log \left( \frac{f_1}{f_2} \right) \wedge \cdots \wedge
d\log \left( \frac{f_{m-1}}{f_m} \right)
$$
for $f_0,\ldots ,f_m \in \{ \ell_0 ,\ldots ,\ell_m ,h_0,\ldots h_m \}$.
We consider two systems $\{ \vph_k \}_{k=0}^m$ and $\{ \psi_k \}_{k=0}^m$
given as
\begin{align*}
  & \vph_k :=\phi (h_0 ,\ldots ,h_{k-1}, \ell_{k-1} ,h_{k+1} ,\ldots h_m) , \\
  & \psi_k :=\phi (h_0 ,\ldots ,h_{k-1}, \ell_k ,h_{k+1} ,\ldots h_m).
\end{align*}
Using the coordinates $t_j=T_j/T_0\ (1\leq j \leq m)$ of $\C^m =\P^m-L_0$,
we have
\begin{align*}
  \vph_0 &
  =\frac{dt_1 \wedge \cdots \wedge dt_m}{t_m(1-t_1)(t_1-t_2)\cdots (t_{m-1}-t_m)} ,\\
  \psi_0 &
  =\frac{dt_1 \wedge \cdots \wedge dt_m}{(1-t_1)(t_1-t_2)\cdots (t_{m-1}-t_m)} ,\\
  \vph_r &
  =\frac{x dt_1 \wedge \cdots \wedge dt_m}
   {t_{r-1}(1-xt_m)(1-t_1)(t_1-t_2)\cdots \widehat{(t_{r-1}-t_r)} \cdots (t_{m-1}-t_m)} ,\\
  \psi_r &
  =\frac{dt_1 \wedge \cdots \wedge dt_m}
   {t_r(1-xt_m)(1-t_1)(t_1-t_2)\cdots \widehat{(t_{r-1}-t_r)} \cdots (t_{m-1}-t_m)} ,
\end{align*}
where $1\leq r \leq m$.
Note that the $m$-form $\vph_0$ coincides with that defined in Section \ref{section-THG}.
\begin{Th}\label{C-intersection}
  \begin{align}
      I_c (\vph_i ,\vph_j)&=I_c (\psi_i ,\psi_j)=0  \quad  (i \neq j) ,
      \label{c-int-0} \\
      I_c (\vph_k ,\vph_k)&=(2\pi \sqrt{-1})^m
      \prod_{\substack{0\leq l \leq m\\l\neq k}}
      \frac{b_l-b_k}{(a_l-b_k)(b_l-a_l)}
      \label{c-int-vph-self},\\
      I_c (\psi_k ,\psi_k)&=(2\pi \sqrt{-1})^m
      \prod_{\substack{0\leq l \leq m\\l\neq k}}
      \frac{a_l-a_k}{(b_l-a_k)(b_l-a_l)}
      \label{c-int-psi-self},\\
      I_c (\vph_i ,\psi_j)&=I_c (\psi_j ,\vph_i )
      =\vep_{ij} (2\pi \sqrt{-1})^m
      \frac{(b_i -a_i)(b_j -a_j)}{(b_i -a_j)} \prod_{l=0}^{m} \frac{1}{b_l-a_l}
      \label{c-int-vph-psi},
  \end{align}
  where
  $$
  \vep_{ij}:=\left\{
    \begin{array}{cl}
      -1 & (i\neq j \ {\rm and}\ (i=0 \ {\rm or}\ j=0)), \\
      1 & ({\rm otherwise}).
    \end{array} \right.
  $$
\end{Th}
The following corollary follows from this theorem immediately.
\begin{Cor}\label{cor-cohomology}
  Under the condition (\ref{condition}),
  $\vph_0 ,\ldots ,\vph_m$ form a basis of $H^m (M,\na_{\om})$.
\end{Cor}
\begin{proof}
  Let $C:=\left( I_c (\vph_i,\vph_j) \right) _{i,j=0,\ldots,m}$
  be the intersection matrix.

  Then we have
  \begin{align*}
    \det (C)=(2\pi \sqrt{-1})^{m(m+1)} \prod_{l=0}^{m} \frac{1}{(b_l-a_l)^m}
    \prod_{0 \leq i \neq j \leq m} \frac{b_i-b_j}{a_i-b_j} ,
  \end{align*}
  which does not vanish under the condition (\ref{condition}).
\end{proof}

In the remainder of this section, we prove Theorem \ref{C-intersection}.
According to \cite{M-form},
to evaluate intersection numbers,
we have to blow up $\P^m$ so that the pole divisor of
the pull back of $\om =d\log u$ is normally crossing.
And we need informations of the $m$-forms
around the points at which $m$ components of
the pole divisor intersect.

For $i \neq j,\ j+1$,
let $L_{j,j+1,\dots ,i-1}$ be the exceptional divisor
obtained by blowing up along
$L_j \cap L_{j+1} \cap \cdots \cap L_{i-1} =(T_j=T_{j+1}=\cdots =T_{i-1}=0)$.
The residue of the pull-back of $\om$ along $L_{j,j+1,\dots ,i-1}$ is
\begin{align*}
  \la_{j,j+1,\dots ,i-1}
  =\sum_{l=j}^{i-1} \la_l +\sum_{l=j+1}^{i-1} \mu_l
  =\sum_{l=j}^{i-1} (a_l-b_{l+1}) +\sum_{l=j+1}^{i-1} (b_l-a_l)
  =a_j-b_i
\end{align*}
(recall that the indices are regarded as elements in $\Z/(m+1)\Z$).
Note that for example, $L_{12}$ is an exceptional divisor,
however $L_1$ is not.

First, we investigate the intersections of
$L_1,\ldots ,L_m ,H_0 ,\ldots ,H_m$, and exceptional divisors
obtained by blowing up along $L_j \cap L_{j+1} \cap \cdots \cap L_m \ (1\leq j \leq m-1)$,
in $\C^m =\P^m -L_0$.
By a straightforward calculation in $\P^m -L_0$,
we obtain the following lemma.
\begin{Lem}\label{blowup-Cm}
  We blow up $\P^m -L_0$ along
  $$
  L_j \cap L_{j+1} \cap \cdots \cap L_{m}
  \quad (1\leq j \leq m-1) .
  $$
  In $\{ \vph_0 ,\ldots ,\vph_m ,\psi_0 ,\ldots ,\psi_m \}$,
  only $\vph_0$ and $\psi_j$ have $L_{j,j+1,\ldots,m}$
  as a component of the pole divisor.
  Further, we have
  $$
  H_k \cap L_{j,j+1,\ldots,m} =\emptyset
  \Longleftrightarrow k=0 \ {\rm or}\ k=j.
  $$

\end{Lem}

Second, we describe the all intersections of
$L_0,\ldots ,L_m ,H_0 ,\ldots ,H_m$, and exceptional divisors.
We use the combinatorial structure of them, which arise from
the similarity between the expression of $u$ on $\P^m-L_0$
and that on $\P^m -L_k$.
\begin{Lem}\label{blow-up}
  After blowing up along all $L_j \cap L_{j+1} \cap \cdots \cap L_{i-1}$
  (with a suitable order),
  the pole divisor of the pull-back of $\om$ is normally crossing.
  Let $\Phi_k$ (resp. $\Psi_k$) be a set consisting of the components
  of the pole divisor of the pull-back of
  $\vph_k$ (resp. $\psi_k$). Then we have
  \begin{align*}
    \Phi_k &=\{
    H_{k+1},\ H_{k+2},\ldots ,H_{k-1},\
    L_{k+1, k+2,\ldots ,k-1},\ L_{k+2,\ldots ,k-1},
    \ldots ,\ L_{k-2,k-1},\ L_{k-1} \} ,\\
    \Psi_k &= \{
    H_{k+1},\ H_{k+2},\ldots ,H_{k-1},\
    L_{k},\ L_{k,k+1},
    \ldots ,\ L_{k,k+1,\ldots ,k-3},\ L_{k,k+1 \ldots ,k-3, k-2}  \}.
  \end{align*}
  Moreover, we have
  $$
  H_k \cap L_{j,j+1,\ldots,i-1} =\emptyset
  \Longleftrightarrow k=i \ {\rm or}\ k=j.
  $$

\end{Lem}
\begin{proof}
  Recall that $u$ is expressed as
  \begin{align*}
    u=t_1^{\la_1} \cdots t_m^{\la_m} \cdot
    (1-xt_m)^{\mu_0} (1-t_1)^{\mu_1}
    \cdot (t_1-t_2)^{\mu_2} \cdots (t_{m-1}-t_m)^{\mu_m}
  \end{align*}
  on $\C^m =\P^m -L_0$
  (with coordinates $t_j=T_j/T_0 \ (1\leq j \leq m)$).
  On the other hand, on $\P^m-L_k$,
  it is expressed as
  \begin{align*}
    u=&s_0^{\la_0} \cdots s_{k-1}^{\la_{k-1}} s_{k+1}^{\la_{k+1}} \cdots s_m^{\la_m} \\
    &\cdot (s_0-xs_m)^{\mu_0}(s_0-s_1)^{\mu_1} \cdots (s_{k-1}-1)^{\mu_{k}}(1-s_{k+1})^{\mu_{k+1}}
    \cdots (s_{m-1}-s_m)^{\mu_m} \\
    =& s_{k+1}^{\la_{k+1}} \cdots s_m^{\la_m} s_0^{\la_0} \cdots s_{k-1}^{\la_{k-1}}
    \cdot (s_{k-1}-1)^{\mu_k} (1-s_{k+1})^{\mu_{k+1}} \\
    &\cdot (s_{k+1}-s_{k+2})^{\mu_{k+2}} \cdots (s_{m-1}-s_m)^{\mu_m}
    (s_0-xs_m)^{\mu_0}(s_0-s_1)^{\mu_1} \cdots (s_{k-2}-s_{k-1})^{\mu_{k-1}} ,
  \end{align*}
  in terms of coordinates $s_j=T_j/T_k \ (0\leq j \leq m,\ j\neq k)$.
  Thus,
  $$
  L_{k+1} ,\ldots ,L_m ,L_0 ,\ldots ,L_{k-1} \ {\rm and} \
  H_{k} ,\ldots ,H_m ,H_0 ,\ldots ,H_{k-1}
  $$
  in $\P^m -L_k$ behave similarly to
  $$
  L_1 ,\ldots ,L_m \ {\rm and} \
  H_0 ,\ldots ,H_m
  $$
  in $\P^m -L_0$.
  Then we obtain this lemma by Lemma \ref{blowup-Cm}.
\end{proof}
\begin{Rem}
  The slight differences come from the signs of
  $s_0-xs_m$ and $s_{k-1}-1$ at the intersection points.
  As mentioned below, these differences make
  complexity of $\vep_{ij}$.
\end{Rem}

In particular, we have $\# \Phi_k =\# \Psi_k =2m$.
We put
\begin{align*}
  \Phi_k^{(m)}:=\left\{
    \{ D_1,\ldots,D_m \} \subset \Phi_k \mid
    D_i \neq D_j \ (i\neq j),\
    D_1 \cap \cdots \cap D_m \neq \emptyset
  \right\}
\end{align*}
($\Psi_k^{(m)}$ is also defined in a similar way).
Then Lemma \ref{blow-up} implies
\begin{align*}
  \Phi_k^{(m)} =&\left\{
    \{ H_p \}_{p\in I} \cup \{ L_{q,q+1,\ldots ,k-1} \}_{q\not\in I}
    \mid I\subset \{ k+1, k+2,\ldots ,m,0, \ldots ,k-1 \}
  \right\} ,\\
  \Psi_k^{(m)} =&\left\{
    \{ H_p \}_{p\in I} \cup \{ L_{k,k+1,\ldots ,q-1} \}_{q\not\in I}
    \mid I\subset \{ k+1, k+2,\ldots ,m,0, \ldots ,k-1 \}
  \right\} .
\end{align*}
Finally, we evaluate the intersection numbers of
$\vph_i$'s and $\psi_j$'s
by using results in \cite{M-form}.
\begin{proof}[Proof of Theorem \ref{C-intersection}]
  First, we obtain (\ref{c-int-0}), since it is clear that
  $$
  \Phi_i^{(m)} \cap \Phi_j^{(m)}
  =\Psi_i^{(m)} \cap \Psi_j^{(m)} =\emptyset \quad (i \neq j).
  $$
  Second, we have
  \begin{align*}
    I_c (\vph_k,\vph_k) &=(2\pi \sqrt{-1})^m
    \sum_{I\subset \{ k+1, k+2, \ldots ,k-1 \}}
    \prod_{i\in I} \frac{1}{\mu_i}
    \cdot \prod_{j\not\in I} \frac{1}{\la_{j,j+1,\ldots ,k-1}} \\
    &=(2\pi \sqrt{-1})^m
    \sum_{I\subset \{ k+1, k+2, \ldots ,k-1 \}}
    \prod_{i\in I} \frac{1}{b_i-a_i}
    \cdot \prod_{j\not\in I} \frac{1}{a_j-b_k}.
  \end{align*}
  By induction on $m$,

  we can show that
  \begin{align*}
    \sum_{I\subset \{ k+1, k+2, \ldots ,k-1 \}}
    \prod_{i\in I} \frac{1}{b_i-a_i}
    \prod_{j\not\in I} \frac{1}{a_j-b_k}
    =\prod_{\substack{0\leq l \leq m \\ l\neq k}}
    \frac{b_l-b_k}{(a_l-b_k)(b_l-a_l)},
  \end{align*}
  which implies (\ref{c-int-vph-self}).
  The equality (\ref{c-int-psi-self}) can be shown
  in a similar way.
  Finally, we prove (\ref{c-int-vph-psi}).
  Because of
  \begin{align*}
    \Phi_i^{(m)} \cap \Psi_i^{(m)}
    &= \left\{ \{ H_0 ,\ldots ,H_m \} -\{ H_i \} \right\}, \\
    \Phi_i^{(m)} \cap \Psi_j^{(m)}
    &= \left\{ \{ H_0 ,\ldots ,H_m ,L_{j,j+1 ,\ldots ,i-1} \}
      -\{ H_i,H_j \} \right\} \ (i\neq j),
  \end{align*}
  we have
  \begin{align*}
    I_c (\vph_i ,\psi_i)&
    =\vep'_{ii} \cdot (2\pi \sqrt{-1})^m
    \prod_{l\neq i} \frac{1}{\mu_l}
    =\vep'_{ii} \cdot (2\pi \sqrt{-1})^m
    \prod_{l\neq i} \frac{1}{b_l-a_l}, \\
    I_c (\vph_i ,\psi_j)&
    =\vep'_{ij} \cdot (2\pi \sqrt{-1})^m \cdot
    \frac{1}{\la_{j,j+1,\dots ,i-1}}
    \prod_{l\neq i,j} \frac{1}{\mu_l} \\
    &=\vep'_{ij} \cdot (2\pi \sqrt{-1})^m \cdot
    \frac{1}{a_j -b_i}
    \prod_{l\neq i,j} \frac{1}{b_l-a_l} \quad (i \neq j) ,
  \end{align*}

  where $\vep'_{ij} =\pm 1$. Let us show that
  \begin{align}
    \vep'_{ij}=\left\{
      \begin{array}{cl}
        1 & (i=0 \ {\rm or} \ j=0 \ {\rm or} \ i=j), \\
        -1& ({\rm otherwise}).
      \end{array} \right.
    \label{proof-vep}
  \end{align}

  When we evaluate the intersection number $I_c (\vph_i ,\psi_j)$,
  it is sufficient to consider blowing up along only

  $$
  L_{i+1}\cap L_{i+2}\cap \cdots \cap L_{i-1}, \
  L_{i+2}\cap \cdots \cap L_{i-1}, \ldots ,\
  L_{i-2}\cap L_{i-1}
  $$
  in the coordinate system of $\P^m-L_i$, since
  the pole divisor of $\vph_i$ is normally crossing
  after this blowing-up process.
  Put $\Phi_i^{(m)} \cap \Psi_j^{(m)}=\{\{ G_1,\ldots ,G_m \}\}$,
  and let $g_l$ be the defining linear forms of $G_l$.
  By taking appropriate coordinates $t'_1 ,\ldots ,t'_m$,
  we express $\vph_i \cdot \prod_l g_l$
  and $\psi_j \cdot \prod_l g_l$ around
  the intersection point $G_1 \cap \cdots \cap G_m$ explicitly.
  \begin{enumerate}[(i)]
  \item For $i=j=0$, we have
    \begin{align*}
      & g_l=1-t'_l \ (1\leq l \leq m), \\
      & \vph_0 \cdot \prod_l g_l =\frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {t'_1 \cdots t'_m},\quad
      \psi_0 \cdot \prod_l g_l =dt'_1 \wedge \cdots \wedge dt'_m ,
    \end{align*}
    and the intersection point $G_1 \cap \cdots \cap G_m$ is
    expressed as
    \begin{align*}
      t'_l =1 \ (1\leq l \leq m).
    \end{align*}
  \item For $i=0$ and $j \neq 0$, we have
    \begin{align*}
      & g_j=t'_j ,\ g_l=1-t'_l \ (l\neq j), \\
      & \vph_0 \cdot \prod_l g_l =\frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {t'_1 \cdots \widehat{t'_j} \cdots t'_m (1-t'_j)},\quad
      \psi_j \cdot \prod_l g_l =\frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {1-xt'_1 \cdots t'_m },
    \end{align*}
    and the intersection point $G_1 \cap \cdots \cap G_m$ is
    expressed as
    \begin{align*}
      t'_j =0 ,\quad t'_l =1 \ (l \neq j).
    \end{align*}
  \item For $i\neq 0$ and $j=i$, we have
    \begin{align*}
      & g_{m+1-i}=t'_{m+1-i} -x,\
      g_l=1-t'_l \ (l \neq m+1-i ), \\
      & \vph_i \cdot \prod_l g_l =x\cdot \frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {t'_1 \cdots t'_m},\quad
      \psi_0 \cdot \prod_l g_l =dt'_1 \wedge \cdots \wedge dt'_m ,
    \end{align*}
    and the intersection point $G_1 \cap \cdots \cap G_m$ is
    expressed as
    \begin{align*}
      t'_{m+1-i} =x ,\quad t'_l =1 \ (l \neq m+1-i).
    \end{align*}
  \item For $i\neq 0$ and $j=0$, we have
    \begin{align*}
      & g_{m+1-i}=t'_{m+1-i},\ g_l=1-t'_l \ (l \neq  m-i+1), \\
      & \vph_i \cdot \prod_l g_l =x\cdot \frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {t'_1 \cdots \widehat{t'_{m+1-i}} \cdots t'_m (t'_{m+1-i}-x)},\\
      & \psi_0 \cdot \prod_l g_l =\frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {t'_1 \cdots t'_m-1}
    \end{align*}
    and the intersection point $G_1 \cap \cdots \cap G_m$ is
    expressed as
    \begin{align*}
      t'_{m+1-i} =0 ,\quad t'_l =1 \ (l \neq m+1-i).
    \end{align*}
  \item For $i\neq 0$ and $j \neq 0,i$, we have
    \begin{align*}
      & g_{j-i} =t'_{j-i},\ g_{m+1-i}=t'_{m+1-i}-x ,\
      g_l =1-t'_l \ (l\neq j-i,m+1-i),  \\
      & \vph_i \cdot \prod_l g_l =x\cdot \frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {t'_1 \cdots \widehat{t'_{j-i}} \cdots t'_m (1-t'_{j-i})},\quad
      \psi_0 \cdot \prod_l g_l =\frac{dt'_1 \wedge \cdots \wedge dt'_m}
      {t'_1 \cdots t'_m-1}
    \end{align*}
    (note that if $j<i$ then we regard $j-i$ as $m+1+j-i$),
    and the intersection point $G_1 \cap \cdots \cap G_m$ is
    expressed as
    \begin{align*}
      t'_{j-i} =0,\quad t'_{m+1-i} =x ,\quad t'_l =1 \ (l \neq j-i, m+1-i).
    \end{align*}
  \end{enumerate}

  Hence we have (\ref{proof-vep}), and
  complete the proof of (\ref{c-int-vph-psi}).
\end{proof}

\section{Twisted homology groups and intersection numbers}\label{section-cycle}
In this section, we construct $m+1$ twisted cycles in $M$ corresponding to
the solutions (\ref{series-sol}) to $\GHE$.

For $0 \leq k \leq m$, we set
\begin{align*}
  M _k :=\C ^m
  -\left( \bigcup _{j=1}^m \Bigl( (z_j =0) \cup (1-z_j=0) \Bigr)
    \cup \Bigl( z_k-x\prod_{j\neq k}z_j =0 \Bigr) \right) ,
\end{align*}
where $z_1,\ldots, z_m$ are coordinates of $\C^m$.
Let $u_k$ and $\phi_k$ be
a multi-valued function and an $m$-form on $M_k$ defined as
\begin{align*}
  & u_k :=\prod _{j \neq k}  z_j ^{a_j -b_k} (1-z_j)^{b_j-a_j}
  \cdot z_k^{a_k} (1-z_k)^{-a_0} \left( z_k-x\prod_{j\neq k} z_j \right) ^{b_k -a_k}, \\
  & \phi_k  :=\frac{dz_1 \wedge \cdots \wedge dz_m}
  {z_k \cdot \prod _{j \neq k} (1-z_j) \cdot (z_k -x \prod_{j\neq k} z_j)} ,
\end{align*}
respectively.

Here, we regard $z_0$ as $1$; we have
\begin{align*}
  & z_0-x\prod_{j\neq k}z_j =1-x\prod_{i=1}^m z_i , \\
  & u_0=\prod_{i=1}^m z_i ^{a_i} (1-z_i)^{b_i-a_i}
  \cdot \left( 1-x \prod_{i=1}^m z_i  \right) ^{-a_0} ,\quad
  \phi_0 =\frac{dz_1 \wedge \cdots \wedge dz_m}{\prod_{i=1}^m \bigl( z_i (1-z_i) \bigr)} .

\end{align*}
We construct a twisted cycle $\tilde{\De }_k$ loaded by $u_k$ in $M_k$.
Let $x$ and $\vep$ be positive real numbers satisfying
$$
\vep <\frac{1}{2},\quad
x <\frac{\vep}{(1+\vep)^{m-1}}
$$
(for example, if
$$
\vep =\frac{1}{3} ,\ 0<x<\frac{1}{3} \cdot \left( \frac{3}{4} \right)^{m-1} ,
$$
this condition holds).
Thus the direct product
\begin{align*}
  \sigma_k :=\left\{ (z_1 ,\ldots ,z_m )\in \R^m \mid
    \vep \leq z_k \leq 1-\vep \ (1\leq r \leq m)
  \right\}
\end{align*}
of $m$ intervals
is contained in the bounded domain
$$
\left\{ (z_1 ,\ldots ,z_m )\in \R^m \ \Big| \  0<z_j<1, \
z_k > x \cdot \prod_{j \neq k} z_j \right\} \subset (0,1)^m.
$$

The orientation of $\sigma _k$
is induced from the natural embedding $\R^m \subset \C^m$.

By using the $\vep$-neighborhoods of
$C_1 :=(z_1 =0)$, $\ldots$, $C_m :=(z_m =0)$, $C_{m+1} :=(1-z_1=0)$, $\ldots$, $C_{2m} :=(1- z_m =0)$,
we construct a twisted cycle $\tilde{\De}_k$
from $\sigma _k \otimes u_k$ in a similar way in \cite{G-FC} and \cite{G-FA}.

If $k\neq 0$,
we have to consider the difference of branches of
$$
z_k^{a_k}  \left( z_k-x\prod_{j\neq k} z_j \right) ^{b_k -a_k}
$$
at the ending and starting points of a circle surrounding $C_k$.

Indeed, for fixed positive real numbers $z_j \ (j\neq k)$,
the solution $x\prod_{j\neq k} z_j$ of the equation
$z_k-x\prod_{j\neq k} z_j =0$ belongs to $\R$ and satisfies
\begin{align*}
  x \cdot \prod_{j \neq k} z_j < x <\vep .
\end{align*}
Thus, the difference is
$\exp (2\pi \sqrt{-1}a_k) \exp (2\pi \sqrt{-1}(b_k -a_k))$ and
the exponent about this contribution is
$$
a_k +(b_k -a_k) =b_k.
$$
The exponents about the contributions
of the circles surrounding $C_{m+k}$, $C_j$, $C_{m+j}$ $(j \neq k)$
are simply
$$
-a_0 ,\ a_j -b_k ,\ b_j -a_j ,
$$
respectively.

\begin{Rem}
  If $k=0$, the exponents about the contributions
  of the circles surrounding $C_i$, $C_{m+i}$ $(1\leq i \leq m)$
  are simply $a_i -b_0=a_i$, $b_i -a_i$, respectively.
  Since $\overline{(0,1)^m} \cap \{ z \mid 1-x\prod_i z_i=0 \} =\emptyset$,
  the twisted cycle $\tilde{\De}_0$ is the usual regularization of $(0,1)^m \otimes u_0$.
\end{Rem}

\begin{Prop}\label{series-cycle}
\begin{align*}
\int _{\tilde{\De }_0} u_0 \phi_0
=& \prod_{i=1}^m \frac{\Ga(a_i) \Ga(b_i-a_i)}{\Ga(b_i)}
\cdot \GH \para{a_0,\ldots ,a_m}{b_1,\ldots ,b_m}{x} ,\\
\int _{\tilde{\De }_r} u_r \phi_r
=& \frac{\Ga(b_r-1) \Ga(1-a_0)}{\Ga(b_r-a_0)}
\cdot \prod _{\substack{1\leq j \leq m \\ j \neq r}} \frac{\Ga(a_j -b_r +1) \Ga(b_j -a_j)}{\Ga(b_j -b_r +1)} \\
& \cdot
\GH \para{a_0 -b_r +1 ,\ldots ,a_m-b_r +1}{b_1-b_r+1 ,\ldots ,2-b_r ,\ldots ,b_m -b_r+1}{x}
\quad (1\leq r \leq m).
\end{align*}
\end{Prop}
\begin{proof}
  In a similar way to Proposition 4.3 of \cite{G-FC} or Proposition 4.3 of \cite{G-FA},
  we can show this proposition by
  expanding the left hand sides with respect to $x$.
  Note that we use the equalities
  \begin{align*}
    & \int_{\tilde{\De }_0} \prod_{i=1}^m z_i^{a_i+n-1} (1-z_i)^{b_i-a_i-1}dz
    =\prod_{i=1}^m \frac{\Ga (a_i+n) \Ga (b_i-a_i)}{\Ga (b_i+n)},  \\
    & \int _{\tilde{\De }_r} \prod_{j \neq r} z_j ^{a_j -b_r +n} (1-z_j)^{b_j-a_j-1}
    \cdot z_r^{b_r-2-n} (1-z_r)^{-a_0} dz \\
    &=\prod_{j \neq r} \frac{\Ga(a_j-b_r+n+1)\Ga(b_j-a_j)}{\Ga(b_j-b_r+n+1)}
    \cdot \frac{\Ga(b_r-1-n)\Ga(1-a_0)}{\Ga(b_r-a_0-n)},
  \end{align*}
  for a natural number $n$ and $1\leq r \leq m$.
  The second equality follows from the fact that
  the twisted cycle $\tilde{\De }_r$ of the integral can be
  identified with the usual regularization of the domain $(0,1)^m$
  loaded by the multi-valued function
  $$
  \prod_{j \neq r} z_j ^{a_j -b_r +n} (1-z_j)^{b_j-a_j-1}
  \cdot z_r^{b_r-2-n} (1-z_r)^{-a_0}
  $$
  on $\C^m -\bigcup_{j=1}^m \bigl( (z_j=0) \cup (1-z_j =0) \bigr)$.

\end{proof}

We define a bijection $\iota _k :M_k \rightarrow M$ by
\begin{align*}
  & \iota _0 (z_1 ,\ldots ,z_m ):=(t_1 ,\ldots ,t_m );\
  t_s=\prod_{i=1}^s z_i ,\\
  & \iota _r (z_1 ,\ldots ,z_m ):=(t_1 ,\ldots ,t_m );\
  t_s =\prod_{j=1}^s z_j \ (s<r),\
  t_s =\frac{z_r}{x\cdot \prod_{j=s+1}^m z_j} \ (s\geq r) ,
\end{align*}
where $1 \leq r \leq m$.
We also define branches of the multi-valued function $u$
on real chambers in $M$.
Let $D_r \subset \R^m \ (1\leq r \leq m)$ be the chamber defined by
\begin{align*}
  t_j>0\ (1\leq j \leq m),\ 1-xt_m >0,\
  t_{j-1}-t_j>0 \ (j\neq r),\ t_{r-1}-t_r<0 ,
\end{align*}
where we regard $t_0$ as $1$.
On $D_r$,
the arguments of the factors of $u$ are given as follows.
\begin{eqnarray*}
  \begin{array}{|c|c|c|c|}
    \hline
    t_j & 1-xt_m & t_{j-1}-t_j \ (j\neq r) & t_{r-1}-t_r \\ \hline
    0 & 0 & 0 & -\pi \\ \hline
  \end{array}
\end{eqnarray*}
Recall that
on $D =\{ (t_1 ,\ldots ,t_m) \in \R^m \mid 0<t_m <t_{m-1} <\cdots <t_1<1 \}$,
all of the arguments of the factors of $u$ are $0$.

\begin{Th}\label{solutions-cycle}
We define a twisted cycle $\De _k$ in $M$ by
\begin{align*}

  \De _k :=(\iota _k )_{*} (\tilde{\De }_k) .
\end{align*}
Then we have
\begin{align*}
  &\int_{\De_0} u \vph_0
  =\prod_{i=1}^m \frac{\Ga(a_i) \Ga(b_i-a_i)}{\Ga(b_i)} \cdot f_0 ,\\

  &\int_{\De_r} u \vph_0
  =e^{-\pi \sqrt{-1} (b_r-a_r-1)}
  \frac{\Ga(b_r-1) \Ga(1-a_0)}{\Ga(b_r-a_0)}
  \cdot \prod _{\substack{1\leq j \leq m \\ j \neq r}} \frac{\Ga(a_j -b_r +1) \Ga(b_j -a_j)}{\Ga(b_j -b_r +1)}
  \cdot f_r ,

\end{align*}
where $1\leq r \leq m$.

\end{Th}
\begin{proof}
By pulling back $u\vph_0$ under $\iota_0$,
we can show the first claim.
We prove the second one.
On $\De_r$, we have
\begin{align*}
  u=&e^{-\pi \sqrt{-1} (b_r-a_r)}
  (t_r-t_{r-1})^{b_r-a_r} (1-xt_m)^{-a_0} \\
  &\cdot \prod_{j=1}^{m} t_j^{a_j-b_{j+1}} \cdot
  \prod_{\substack{1\leq j \leq m \\ j\neq r}} (t_{j-1}-t_j)^{b_j-a_j} ,
\end{align*}
where the argument of each factor is zero on $\iota_r (\si_r) \subset D_r$.
We consider the pull back of $u \vph_0$ under $\iota_r$:
\begin{align*}
  u(\iota_r (z))
  =&

  e^{-\pi \sqrt{-1} (b_r-a_r)} \cdot x^{-b_r} \cdot u_r (z), \\
  \iota_r^{*} \vph_0
  =&

  -x\cdot \phi_r .
\end{align*}
By Proposition \ref{series-cycle}, we thus have
$$
\int_{\De_r} u \vph_0
=-e^{-\pi \sqrt{-1} (b_r-a_r)} x^{1-b_r} \int _{\tilde{\De }_r} u_r \phi_r
=e^{-\pi \sqrt{-1} (b_r-a_r-1)}  \cdot (\Ga {\textrm -}{\rm factors})\cdot f_r .
$$
\end{proof}

\begin{Rem}
  For $1\leq r \leq m$,
  the twisted cycle $\De_r$ is different from
  the regularization of $D_ r \otimes u$
  as elements in $H_m (\CC_{\bu} (M,u))$.
\end{Rem}
\begin{Rem}
  Let
  $\iota'_r :M_r \to M_0 \ (1\leq r \leq m)$ be the map defined as
  $$
  \iota'_r (z_1 ,\ldots ,z_m ):=(w_1 ,\ldots ,w_m );\
  w_r =\frac{z_r}{x\prod_{j\neq r} z_j} ,\ w_s =z_s \ (s\neq r).
  $$
  Then it is easy to see that
  $\iota_r =\iota_0 \circ \iota'_r$.
\end{Rem}

The replacement $u \mapsto u^{-1} =1/u$ and the construction same as $\De _k$ give
the twisted cycle $\De_k ^{\vee}$
which represents an element in $H_m (\CC_{\bu} (M,u^{-1}))$.
We obtain the intersection numbers of the twisted cycles $\{ \De _k \} _{k=0}^m$ and
$\{ \De _k^{\vee} \}_{k=0}^m$.

\begin{Th}\label{H-intersection}
  \begin{enumerate}[(i)]
  \item For $k\neq l$,
    we have $I_h (\De_k ,\De_l ^{\vee}) =0$.
  \item The self-intersection numbers of $\De_k$'s are as follows:
    \begin{align*}
      I_h (\De _0 ,\De _0^{\vee})
      &= \prod_{i=1}^{m} \frac{\al_i (1-\be_i)}{(1-\al_i)(\al_i -\be_i)} ,\\
      I_h (\De _r ,\De _r^{\vee})
      &= \prod_{\substack{1\leq j \leq m \\ j\neq r}}
      \frac{\al_j (\be_r-\be_j)}{(\be_r-\al_j)(\al_j -\be_j)}
      \cdot \frac{\al_0-\be_r}{(1-\be_r)(\al_0-1)} \quad (1 \leq r \leq m),
    \end{align*}
    where $\al_j :=e^{2\pi \sqrt{-1}a_j} ,\ \be_j :=e^{2\pi \sqrt{-1}b_j}$.
  \end{enumerate}
\end{Th}
\begin{proof}
This theorem can be also shown similarly to
Theorem 4.6 of \cite{G-FC} or Theorem 4.6 of \cite{G-FA}.

\end{proof}
\begin{Cor}\label{cor-homology}
  Under the condition (\ref{condition}), the twisted cycles
  $\De_0 ,\ldots ,\De_m$ form a basis of $H_m (\CC_{\bu} (M,u))$
\end{Cor}
\begin{proof}
  The determinant of the intersection matrix
  $H:=\left( I_h (\De_i,\De_j) \right)_{i,j=0,\ldots ,m}$
  does not vanish.
\end{proof}
\begin{Rem}\label{cf-Mimachi}
  In Section 3 of \cite{Mimachi}, there are the twisted cycles
  $D_1^{(0)} ,\ldots ,D_m^{(0)} ,D_{m+1}^{(0)}$
  which correspond to the solutions $f_1 ,\ldots ,f_m ,f_0$, respectively.
  By the variable change
  $$
  p: (t_1 ,\ldots ,t_m) \longmapsto
  \left( \frac{1}{t_1},\ldots ,\frac{1}{t_m} \right),
  $$
  our integral representation (\ref{integral}) coincides with
  that in \cite{Mimachi}.
  It is easy to see that
  \begin{align*}
    \De_0 =(-1)^m p_*(D_{m+1}^{(0)}) ,\quad
    \De_r =(-1)^m \frac{\be_r -\al_0}{\al_0 (\be_r -1)}
    p_*(D_r^{(0)}) \quad (1 \leq r \leq m)
  \end{align*}
  as elements in $H_m (\CC_{\bu} (M,u))$.
\end{Rem}

\section{Twisted period relations} \label{section-TPR}
The compatibility of the intersection forms and the pairings obtained by integrations
(see \cite{CM}) implies twisted period relations:
\begin{align*}
  C=\Pi_{\om} \tp H^{-1} \tp \Pi_{-\om},
\end{align*}
where $\Pi_{\pm \om}$ are defined as
$$
\Pi_{\om}:=\left( \int _{\De _j} u\vph_i \right)_{i,j},\quad
\Pi_{-\om}:=\left(\int _{\De _j ^{\vee}} u^{-1} \vph_i \right)_{i,j} ,
$$
$C$ and $H$ are the intersection matrices
(see the proof of Corollaries \ref{cor-cohomology} and \ref{cor-homology}).
Comparing the $(i,j)$-entries of both sides, we obtain the following theorem.

\begin{Th} \label{TPR}
  We have
  \begin{align}
    \label{TPR-eq}
    I_{c} (\vph_i ,\vph_j)
    = \sum_{k=0}^m \frac{1}{I_{h} (\De _k ,\De _k^{\vee} )}
    \cdot \int _{\De _k} u\vph_i \cdot \int _{\De _k ^{\vee}} u^{-1} \vph_j .
  \end{align}

\end{Th}
By using our results, we can reduce
the twisted period relations (\ref{TPR-eq})
to quadratic relations among $\GH$'s.
We write down one of them as a corollary.
\begin{Cor}\label{TPR-cor}
  The equality (\ref{TPR-eq}) for $i=j=0$ is reduced to
  \begin{align*}
    \prod_{l=1}^{m} \frac{b_l-b_0}{a_l-b_0}
    =&\prod_{l=1}^{m} \frac{b_l}{a_l}
    \cdot \GH \para{\boldsymbol{a}}{\boldsymbol{b}}{x}
    \cdot \GH \para{-\boldsymbol{a}}{-\boldsymbol{b}}{x} \\
    &+\sum _{r=1}^{m} x^2 \cdot \frac{a_0(a_0-b_r)(b_r-a_r)}{b_r(b_r^2-1)}
    \cdot \prod _{\substack{1\leq l \leq m \\ l\neq r}} \frac{a_l -b_r}{b_l -b_r} \\
    & \quad \quad \quad \quad \quad
    \cdot \GH \para{\boldsymbol{a}^{r,+}}{\boldsymbol{b}^{r,+}}{x}
    \cdot \GH \para{\boldsymbol{a}^{r,-}}{\boldsymbol{b}^{r,-}}{x},
  \end{align*}
  where
  \begin{align*}
    & \boldsymbol{a} :=(a_1 ,\ldots ,a_{m+1}) ,\
    \boldsymbol{b} :=(b_1 ,\ldots ,b_m) , \\
    & \boldsymbol{a}^{r,\pm} :=(1,\ldots ,1)\pm (a_1-b_r,\dots ,a_{m+1}-b_r) ,\\
    & \boldsymbol{b}^{r,\pm} :=
    (1,\ldots ,1)\pm (b_1-b_r ,\dots ,\pm 1-b_r ,\dots ,b_m-b_r).
  \end{align*}
\end{Cor}
\begin{proof}
  By

  Theorem \ref{solutions-cycle},

  we can express the integrals in (\ref{TPR-eq}) as
  products of $\Ga$-factors and $\GH$.
  By Theorems \ref{C-intersection}, \ref{H-intersection}, and
  the formula $\Ga (w) \Ga (1-w) =\pi/\sin (\pi w)$,
  we obtain the corollary.
\end{proof}

\begin{Rem}
  If we assume the condition (\ref{condition}) and
  $$
  a_i-a_j \not\in \Z \quad (0\leq i<j \leq m),
  $$
  then $\psi_0,\ldots ,\psi_m$ also form a basis of $H^m (M,\na_{\om})$,
  because of Theorem \ref{C-intersection}.
  Considering $I_c (\vph_i ,\psi_j)$, $I_c (\psi_i ,\vph_j)$, or
  $I_c (\psi_i ,\psi_j)$, we obtain other twisted period relations.
\end{Rem}

\section*{Acknowledgments}
The author thanks Professor Keiji Matsumoto for his useful advice and constant encouragement.

config: arxiv


TITLE: Linear maps inducing identity on exterior square
QUESTION [4 upvotes]: Let $V$ be $n$-dimensional space over a field $F$. Let $V\times V\rightarrow \wedge^2 V$ be the natural map. Thus, if $\{v_1,v_2,\ldots, v_n\}$ is a basis of $V$ then $\{v_i\wedge v_j \,\,|\,\, 1\le i<j\le n\}$ is a basis of $\wedge^2V$.

Q. What are the linear maps $\varphi:V\rightarrow V$ which induce identity map on $\wedge^2(V)$? Are such maps well-studied?

Here induced maps on $\wedge^2(V)$ are naturally defined by $T(v\wedge w)=T(v)\wedge T(w)$.

If necessary, assume that $F$ is of characteristic different from $2$.

REPLY [1 votes]: I think, only identity linear map of $V$ induces identity on $\wedge^2 V$ if $\dim V\ge 3$.
If $\dim V=2$, then the group ${\rm SL}(V)$ is the desired set of linear maps inducing identity on $\wedge^2 V$.
Proof for $n\ge 3$:
Let $T:V\rightarrow V$ be such that induced map on $\wedge^2(V)$ is identity.
(1) Consider $v,w$ independent in $V$. Then $T(v\wedge w)=v\wedge w$. It is easy to show that $T$ takes span$\{v,w\}$ to itself.
(2) Let $u$ be arbitrary non-zero vector. Then choose $v,w$, independent vectors such that $\dim$ span$\{u,v\}=2=\dim$ span$\{u,w\}$ and $u,v,w$ are independent.
By (1), $T$ takes span$\{u,v\}$ to itself, and span$\{u,w\}$ to itself; and hence their intersection to itself. This means, $T(u)=\lambda u$ for some $\lambda\in F$.
From this, it is easy to show that $T$
(i) $T$ is scalar matrix
(ii) The scalar matrix must be identity (due to $T(v\wedge w)=v\wedge w$ for all $v,w\in V$).

I hope this is correct.
Edit (After comment by darij grinberg:) (ii) is incorrect; the scalar matrix is $\pm $ identity. So for $\dim V\ge 3$, $\pm I$ are the only maps inducing identity on $\wedge^2 V$.


TITLE: Let $f:[a, b]\rightarrow\mathbb{R}$ be differentiable. If $f'(a)=f'(b)$, then exists a $c \in (a, b)$, such that $f'(c) = \frac{f(c) - f(a)}{c - a}$
QUESTION [3 upvotes]: In the book (Curso de Análise, volume 1,Elon Lages), there is a suggestion that helps a lot.
First, consider that $$f'(a) =f'(b)=0$$ Then, consider the function $g:[a,b] \rightarrow \mathbb{R}$, where $g(x) = \frac{f(x) - f(a)}{x - a}$ and $g(a) = 0$. Show that $g$ reaches it's maximum or minimum in a point $c \in (a,b)$. For the general case, consider $$g(x) = f(x) - xf'(a)$$
I can see why the first case: if a take the derivative of g, I end up with something like:
$$g'(x) = \frac{1}{x - a} \left( f'(x) - \frac{f(x) - f(a)}{x - a} \right)$$
So, by being continuous (from the differentiable hypothesis) on a compact set, by Weierstrass's Theorem, we have that $g$ must have it's maximum/minimum on $c \in [a,b]$. By being a critical point, we must have $g'(c) = 0$, and assuming $c \neq a$, we have our first conclusion.
But (1) I can't see why it must be a interior point (seriously, I've been on this question for 4 days), and (2) the second suggestion isn't that clear for me.
Any other ideas for solutions will be of great help to me.

REPLY [4 votes]: There are several steps involved in the first part and here are some hints:
If $g$ does not have  a local minimum or a local maximum in $(a,b)$ then $g$ is necessarily strictly monotonic. This implies that $f$ is concave or convex (depending on whether $g$ is increasing or decreasing). Hence $f'$ is monotonic. The fact that $f'(a)=f'(b)=0$ shows that $f'\equiv 0$ and $f$ is a constant. So any $c \in (a,b)$ is good enough.
The second part is straightforward. Just apply the first part to $g(x)=f(x)-xf'(a)$. Since $g'(a)=g'(b)=0$ this is possible). Simplify the equation $g'(c)=\frac {g(c)-g(a)} {c-a}$ to finish the proof.


TITLE: How to solve $y(x) y'(x) +C_1y(x)^2+C_2y(x)={1\over2}C_3$
QUESTION [3 upvotes]: $$y(x) y'(x) +C_1y(x)^2+C_2y(x)={1\over2}C_3
$$
C1, C2 , C3 are constants.
how to solve this equation??

REPLY [4 votes]: Hint:
With suitable constant substitutions, you can rewrite as $$\frac{yy'}{y^2+2ay+b}=c.$$
Then completing the square
$$\frac{yy'}{y^2+2ay+b}=\frac{yy'}{(y+a)^2+b-a^2}=\frac{(y+a)-a}{(y+a)^2+d}y'.$$
This will integrate as the logarithm of the denominator, minus an (hyperbolic) arctangent.
$$\alpha\log((y+a)^2+d)-\beta\arctan\left(\frac{y+a}{\sqrt d}\right)=cx+C.$$
Unfortunately, you can't invert this relation.


TITLE: Simplifying $\frac{1/(\frac{1}{z_1}(1-t)+\frac{1}{z_2}t) - z_1}{(z_2 - z_1)}$
QUESTION [3 upvotes]: This drives me mad! I am not very good in math but thought I could at least do basic things like this one, but can't figure it out and I spent a day on it. I am trying to simplify:
$\dfrac{\dfrac{1}{\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t} - z_1}{(z_2 - z_1)}$
In Wolfram Alpha it shows me that the solution is:
$\dfrac{tz_1}{t(z_1-z_2)+z_2}$
Which I know is right, but I simply can't figure out the steps to get there. If someone could please help me. I have been as far as doing:
$\dfrac{\dfrac{1 - z_1(\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t)} {\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t}}{(z_2 - z_1)}$
$\dfrac{1 - z_1(\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t)} {(\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t)(z_2 - z_1)}$
And then develop the terms from there, etc. but I just can't get to the equation:
$\dfrac{tz_1}{t(z_1-z_2)+z_2}$

REPLY [2 votes]: Starting from where you left off, multiply the top and bottom by $z_1z_2$ to get rid of the fractions, then expand the numerator:
$$
\require{cancel}
\begin{align}
\dfrac{1 - z_1(\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t)} {(\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t)(z_2 - z_1)} &= \dfrac{z_1z_2\Big(1 - z_1(\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t)\Big)} {z_1z_2\Big((\dfrac{1}{z_1}(1-t)+\dfrac{1}{z_2}t)(z_2 - z_1)\Big)} \\
&= \dfrac{z_1z_2 - z_1(z_2(1-t)+z_1t)}{(z_2(1-t)+z_1t)(z_2 - z_1)} \\
&= \dfrac{\cancel{z_1z_2} - \cancel{z_1z_2} + z_1z_2t - z_1^2t}{(z_2(1-t)+z_1t)(z_2 - z_1)} \\
&= \dfrac{z_1t(z_2 - z_1)}{(z_2(1-t)+z_1t)(z_2 - z_1)}
\end{align}$$
Now cancel the common factor and expand the denominator.


TITLE: How to derive 3 complementary mutually independent events using the addition rule
QUESTION [1 upvotes]: I'm stuck with following derivation of showing the independence of 3 complementary events using the addition rule. My knowledge is a bit rusty.
$P(A^c \cap B^c \cap C^c )= 1 - [P(A)+P(B)+P(C)-P(A \cap B)-P(A \cap C)-P(B \cap C)+ P(A \cap B \cap C)]$
$ = P(A)P(B)P(C)-P(A)P(B)-P(A)P(C)-P(B)P(C)-P(A)-P(B)-P(C)+1 $
= ... (how to further derive?)
$= (1-P(A))(1-P(B))(1-P(C))$
$=P(A^c)P(B^c)P(C^c)$
Thanks a lot for the help

REPLY [1 votes]: There is a mistake in your second line
$P(A^c \cap B^c \cap C^c )= 1 - [P(A)+P(B)+P(C)-P(A \cap B)-P(A \cap C)-P(B \cap C)+ P(A \cap B \cap C)]$
$ = \color{red}-P(A)P(B)P(C)\color{red}+P(A)P(B)\color{red}+P(A)P(C)\color{red}+P(B)P(C)-P(A)-P(B)-P(C)+1 $
$= (1-P(A))(1-P(B))(1-P(C))$ [by factorization]
$=P(A^c)P(B^c)P(C^c)$


TITLE: Why does this setting imply that a category is Grothendieck?
QUESTION [11 upvotes]: I came across the following Lemma in Mitsuyasu Hashimoto's Equivariant Twisted Inverses; it is Lemma 11.2 on page 107 of this pdf.
Let $\mathcal{A}$ be an abelian category which satisfies the (AB3) condition (i.e., is cocomplete) and $\mathcal{B}$ a Grothendieck category. Assume we have an adjoint pair
$$ F \colon \mathcal{A} \rightleftarrows \mathcal{B} :G$$
such that $F$ is faithful exact and $G$ preserves filtered colimits. Then $\mathcal{A}$ is also Grothendieck.
Sadly, the proof is not given there but at least should work similar to the one before, where "Grothendieck" is replaced by "locally noetherian". Since one easily deduces the exactness of filtered colimits in $\mathcal{A}$, it remains to show that $\mathcal{A}$ admits a generator. But somehow I am confused between the notion of a generator/generating set in the sense of a separator (detecting non-trivial morphisms) and being able to write an object as a filtered colimit over a diagram involving only the generator. What is the connection between these notions?
Possible application: This statement would immediately give that the category of comodules over a flat Hopf algebroid $(A,\Gamma)$ is Grothendieck -- take $F$ to be the forgetful functor from $\Gamma$-comodules to $A$-modules and let $G$ be the cofree comodule.

REPLY [5 votes]: Here's a rather convoluted proof of this lemma. It suffices to show that $\mathcal A$ is accessible, that is, $\mathcal A\simeq Ind_\kappa(\mathcal A_0)$ for some small category $\mathcal A_0$ (the sum of all objects in $\mathcal A_0$ is then a generator in $\mathcal A$). Since $F$ is faithful and exact, the adjunction is comonadic (Barr-Beck), and the comonad preserves filtered colimits by the assumption on $G$. In particular, the comonad is accessible, i.e., it preserves $\kappa$-filtered colimits for some regular cardinal $\kappa$. It is well-known that coalgebras for an accessible comonad on a locally presentable category form a locally presentable category: see Prop A.1 in http://www.math.harvard.edu/~eriehl/coalgebraic.pdf (this is basically a special case of the Makkai-Paré theorem stating that lax limits of accessible categories are accessible, Theorem 2.77 in Adámek-Rosicky).


text:
\section{A numerical test \label{sec:numerical_test} }
To validate our theoretical findings, we perform a two-dimensional convergence test for the Galerkin discretization scheme \eqref{eq:SBM-formulation-1} with penalty parameter $\gamma = 10$ in the domain $\Om$ shown in Figure \ref{fig:NumericalTest_NonSmoothBoundary}. The domain $\Omega$ exhibits a re-entrant corner $C$ of amplitude $\omega=\frac{3\pi}2$, formed by two slightly curved edges. The exact solution, in a polar coordinate system $(\varrho, \theta)$ centered at $C$, is given by
\begin{equation} \label{eq:sol-test}
u(\varrho, \theta) = \varrho^{2/3} \, \sin(2\theta/3  + \pi/6 )
\end{equation}

Figure \ref{fig:numerical_solutions_convRates} displays the surrogate domain and boundary for a given mesh, the corresponding numerical solution and the error dacay rates on $u$ and $\nabla u$ in the $L^{2}(\ti{\Om})$-norm. It is apparent from this test involving a re-entrant corner, that the actual convergence rate in  the  energy norm is coherent with our theoretical prediction  given in Theorem \ref{theo:estim-discr-err-a}, as observed in Figure \ref{fig:gradU_convRate}; indeed, our solution $u$ belongs to $H^{1+r}(\Omega)$ for any $r < \tfrac23$.  On the other hand, Theorem \ref{theo:estim-L2-err} predicts a convergence rate in  the $L^2$-norm not smaller than $\tfrac76$, whereas the optimal rate is slightly larger, namely $\tfrac43$;
Figure \ref{fig:U_convRate} indicates that the latter is probably the actual rate, in accordance with the heuristic considerations given in Remark \ref{re:non-optimality}.
 The actual error values and numerical convergence rates are reported in Table~\ref{table1}.
\begin{figure}
	\centering
\begin{tikzpicture}
\begin{axis}[
axis x line=none,
axis y line=none,
domain=-0.6:0.6,
samples=1001,
disabledatascaling,
xticklabels=\empty,
]
\addplot [black,line width = 0.25mm] {-abs(rad(atan(x)))};
\addplot [black,line width = 0.25mm] {0.55};
\addplot [mark=none,black,line width = 0.25mm] coordinates {(0.6, 0.55) (0.6, -0.54)};
\addplot [mark=none,black,line width = 0.25mm] coordinates {(-0.6, 0.55) (-0.6, -0.54)};
\draw[black,->,-stealth] (0.0707106*0.75,-0.0707106*0.75) arc (-45:225:0.075);
\node[text width=0.2cm] at (0,0.125) { $\omega$};
\dimline[extension start length =0,extension end length = 0,line style = {line width=0.7}]{(-0.6,0.62)}{(0.6,0.62)}{$L$};
\dimline[extension start length =0,extension end length = 0,line style = {line width=0.7}]{(-0.69,-0.54)}{(-0.69,0.55)}{$D$};
\fill (0,0) circle (0.5mm);
\node[text width=0.25cm] at (0,-0.1) { $C$};
\end{axis}
\end{tikzpicture}
	\caption{Domain $\Om$ with $\omega = 3\pi/2$, $C=(0,0)$, $L = 1.2$ and $D = 0.55+ \arctan(0.6)$.}
\label{fig:NumericalTest_NonSmoothBoundary}
\end{figure}
\begin{figure}[t!]\centering
\begin{subfigure}{0.46\textwidth}\centering
	\includegraphics[width=1\linewidth]{\Figures/surrogate.png}
	\label{fig:efig1}
	\caption{Surrogate domain $\tO$ (grey) with corresponding mesh, true boundary $\G$ (blue) and surrogate boundary $\tG$ (red).}
\end{subfigure}
\qquad
\begin{subfigure}{0.46\textwidth}\centering
	\includegraphics[width=1\linewidth]{\Figures/numerical_solution.png}
	\label{fig:efig2}
	\caption{Numerical solution $u_h$.}
\end{subfigure}
\\[.3cm]
\begin{subfigure}[b]{0.46\linewidth}
	\centering
	\begin{tikzpicture}[scale= 0.75]
	\begin{loglogaxis}[
	grid=major,x post scale=1.0,y post scale =1.0,
	xlabel={h},ylabel={},
	legend style={font=\footnotesize,legend cell align=left},
	legend pos= north west,
	axis equal	]
	\addplot[ mark=x,blue,line width=1pt] coordinates {
		(0.000633897,0.0000162644)
		(0.00126778,0.000035424)
		(0.0025355,0.0000904343)
		(0.00507076,0.000240725)
		(0.010141,0.000669068)
		(2.027730E-02,0.00174916)
		(0.0405394,0.00434224)
		(0.0810849,0.00901982)
	};
	\addplot[black,line width=1pt] coordinates {
	(3E-3,2*0.0000356359487256136)
	(6E-3,0.00016)
	(6E-3,2*0.0000356359487256136)
	(3E-3,2*0.0000356359487256136)
};
	\end{loglogaxis}
	\node[text width=0.6cm] at (3.8,1.8) {\footnotesize $\frac{7}{6}$};
	\end{tikzpicture}
	\caption{Convergence rate of $u_h$ to $u$ in $L^{2}$-norm.}
	\label{fig:U_convRate}
\end{subfigure}
\qquad
\begin{subfigure}[b]{0.46\linewidth}
	\centering
	\begin{tikzpicture}[scale=0.75]
	\begin{loglogaxis}[
	grid=major,x post scale=1.0,y post scale =1.0,
	xlabel={h},ylabel={},
	legend style={font=\footnotesize,legend cell align=left},
	legend pos= north west,
	axis equal	]
	\addplot[ mark=x,blue,line width=1pt] coordinates {
		(0.000633897,0.00397341)
		(0.00126778,0.0072572)
		(0.0025355,0.00986189)
		(0.00507076,0.0150105)
		(0.010141,0.0236991)
		(2.027730E-02,0.0375139)
		(0.0405394,0.0593803)
		(0.0810849,0.122044)
	};
	\addplot[black,line width=1pt] coordinates {
	(3E-03,0.008)
	(6E-3,0.0126992084157456)
	(6E-3,0.008)
	(3E-3,0.008)
};
	\end{loglogaxis}
	\node[text width=0.2cm] at (3.5,1.9) {\footnotesize $\frac{2}{3}$};
	\end{tikzpicture}
		\caption{Convergence rate of $\nabla u_h$ to $\nabla u$ in $L^{2}$-norm.}
		\label{fig:gradU_convRate}
\end{subfigure}
	\caption{Surrogate domain $\tO$, numerical solution $u_h$, and convergence rates of the error $u-u_h$ in the $L^{2}$-norm and $H^1$-seminorm.}
\label{fig:numerical_solutions_convRates}
\end{figure}
\begin{table}[hbt!]\centering
	\begin{tabular}{M{1.8cm} | M{2.7cm}  M{1.2cm}  | M{2.7cm}  M{1.2cm} }
		  & \multicolumn{4}{c}{ }  \\
		Mesh Size & $ \, \| \, u - u^h \, \|_{0,\tO} $ & Rate & $ \, \| \, \nabla (u - u^h) \, \|_{0,\tO} $ & Rate \\
		\hline
		8.10E-02 & 9.02E-03 & - & 1.22E-01 & -\\
		4.05E-02 & 4.34E-03 & 1.05 & 5.94E-02 & 1.04 \\
		2.03E-02 & 1.75E-03 & 1.31 & 3.75E-02 & 0.66 \\
		1.01E-02 & 6.69E-04 & 1.39 & 2.37E-02 & 0.66 \\
		5.07E-03 & 2.41E-04 & 1.47 & 1.50E-02 & 0.66 \\
		2.54E-03 & 9.04E-05 & 1.41 & 9.86E-03 & 0.61\\
		1.27E-03 & 3.54E-05 & 1.35 & 7.25E-03 & 0.44\\
	    6.34E-04 & 1.63E-05 & 1.12 & 3.97E-03 & 0.87 \\
	\end{tabular}
	\caption{ Convergence rates for the Poisson equation with solution \eqref{eq:sol-test} using the SBM approach.
		\label{table1} }
\end{table}
\clearpage