Proof of Ishii's Lemma: Test Data and Matrix Bounds at a Maximum of a Quadratically Penalised Difference

Throughout, $n$, $\Omega$, $u$, $v$, $\alpha$, $\hat{x}$, $\hat{y}$, $\delta$ and $p$ are as in the statement. Put $\hat{z}=\iota(\hat{x},\hat{y})$ and

$$\Omega^{\ast}=\{\,\iota(\xi,\eta)\ :\ \xi\in\Omega,\ \eta\in\Omega\,\}\subseteq\mathbb{R}^{2n},$$

which is open by Twice Differentiability of a Sum in Separated Variables (i).

Conventions. We use without further comment that $\le$ on $\mathbb{R}$ is transitive and compatible with addition, by the ordered field axioms and Total Order on a Set, and the weak compatibility with multiplication: if $0\le b$ and $s\le t$, then $sb\le tb$; this is immediate when $b=0$ or $s=t$, and otherwise follows from claim 10 of Elementary Order Arithmetic in an Ordered Field. Recall from Euclidean Space and Real Matrices: Standing Notation (iv) that $P\preceq Q$ means $w\cdot(Pw)\le w\cdot(Qw)$ for every $w$, and that $\preceq$ is transitive.

Step 1 (The doubled data). Let $-v:\Omega\to\mathbb{R}$ be the function whose value at $\eta\in\Omega$ is $-v(\eta)$; it is upper semicontinuous on $\Omega$ by claim 1 of Negation, Restriction, and Separated Differences of Semicontinuous Functions, applied at every point of $\Omega$. Let $w:\Omega^{\ast}\to\mathbb{R}$ be the function determined by

$$w\bigl(\iota(\xi,\eta)\bigr)=u(\xi)+(-v)(\eta)\qquad(\xi,\eta\in\Omega),$$

which is well defined because $\iota$ is injective.

By The Doubling Matrix and its Elementary Properties (v) the matrix $\alpha J$ lies in $\mathcal{S}(2n)$, so claim 1 of Quadratic and Affine Functions of Class $C^2$, Translation, and Quadratic Perturbation of Semiconvexity, applied with $M=\alpha J$, $q=0_{\mathbb{R}^{2n}}$ and $c=0$, shows that the function $Q:\mathbb{R}^{2n}\to\mathbb{R}$ given by $Q(z)=\tfrac{1}{2}\,z\cdot\bigl((\alpha J)z\bigr)$ is of class $C^{2}$ on $\mathbb{R}^{2n}$, with

$$DQ(z)=(\alpha J)z,\qquad D^{2}Q(z)=\alpha J\qquad\text{for every }z\in\mathbb{R}^{2n}.$$

Moreover, for $\xi,\eta\in\mathbb{R}^{n}$, claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, claim 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite and The Doubling Matrix and its Elementary Properties (ii) give

$$Q\bigl(\iota(\xi,\eta)\bigr)=\tfrac{1}{2}\,\alpha\,\Bigl(\iota(\xi,\eta)\cdot\bigl(J\,\iota(\xi,\eta)\bigr)\Bigr)=\tfrac{\alpha}{2}\lVert\xi-\eta\rVert^{2}.$$

Step 2 (A local maximum of $w-Q$). Let $z\in\Omega^{\ast}$ satisfy $d_{E}(z,\hat{z})<\delta$, and let $(x,y)$ be the unique pair with $z=\iota(x,y)$, so that $x,y\in\Omega$. By claim 4 of Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space we have $d_{\times}\bigl((x,y),(\hat{x},\hat{y})\bigr)\le d_{E}(z,\hat{z})$, where $d_{\times}$ is the product metric obtained from $d_{E}$ and $d_{E}$, and by claim 2 of The Product Metric is a Metric both $d_{E}(x,\hat{x})$ and $d_{E}(y,\hat{y})$ are at most $d_{\times}\bigl((x,y),(\hat{x},\hat{y})\bigr)$. Hence $d_{E}(x,\hat{x})<\delta$ and $d_{E}(y,\hat{y})<\delta$ by claim 2 of Elementary Order Arithmetic in an Ordered Field, so the hypothesis of the statement applies to the pair $x$, $y$ and, by Step 1,

$$(w-Q)(z)=u(x)-v(y)-\tfrac{\alpha}{2}\lVert x-y\rVert^{2}\ \le\ u(\hat{x})-v(\hat{y})-\tfrac{\alpha}{2}\lVert\hat{x}-\hat{y}\rVert^{2}=(w-Q)(\hat{z}).$$

Thus $w-Q$ has a local maximum at $\hat{z}$ relative to $\Omega^{\ast}$.

Step 3 (The theorem on sums). Since $\alpha$ is positive, $\alpha^{-1}$ exists and is positive by claim 7 of Elementary Order Arithmetic in an Ordered Field, and $(\alpha^{-1})^{-1}=\alpha$. We apply Theorem on Sums for Two Upper Semicontinuous Functions with $n_{1}=n_{2}=n$, $\Omega_{1}=\Omega_{2}=\Omega$, $u_{1}=u$, $u_{2}=-v$, $V=\mathbb{R}^{2n}$, the test function $Q$, the point $\hat{z}$ of Step 2 and $\varepsilon=\alpha^{-1}$. Here $A=D^{2}Q(\hat{z})=\alpha J$, and the unique pair $(p_{1},p_{2})$ with $\iota(p_{1},p_{2})=DQ(\hat{z})$ is $(p,-p)$: indeed, by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, The Doubling Matrix and its Elementary Properties (i) and claim 2 of Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space,

$$DQ(\hat{z})=(\alpha J)\hat{z}=\alpha\bigl(J\,\iota(\hat{x},\hat{y})\bigr)=\alpha\,\iota(\hat{x}-\hat{y},\hat{y}-\hat{x})=\iota\bigl(\alpha(\hat{x}-\hat{y}),\ \alpha(\hat{y}-\hat{x})\bigr),$$

and $\alpha(\hat{y}-\hat{x})=\alpha\bigl((-1)(\hat{x}-\hat{y})\bigr)=(-1)\bigl(\alpha(\hat{x}-\hat{y})\bigr)=-p$ in the real vector space $\mathbb{R}^{n}$ of Euclidean Space $\mathbb{R}^n$ is a Real Vector Space.

We obtain $X_{1},X_{2}\in\mathcal{S}(n)$ such that the quadruple $\bigl(\hat{x},u(\hat{x}),p,X_{1}\bigr)$ is approximable by test data from above for $u$ and the quadruple $\bigl(\hat{y},(-v)(\hat{y}),-p,X_{2}\bigr)$ is approximable by test data from above for $-v$, the open set being $\Omega$ in both cases, and such that

$$-\bigl(\alpha+\lVert\alpha J\rVert\bigr)I_{2n}\ \preceq\ X_{1}\oplus X_{2}\ \preceq\ \alpha J+\alpha^{-1}(\alpha J)^{2}.$$

Put $X=X_{1}$ and $Y=-X_{2}$, both elements of $\mathcal{S}(n)$ by Second-Order Equations on Euclidean Open Sets (iii). Since the scalar multiple of a matrix is formed entrywise and two real matrices of the same size are equal exactly when all their entries agree, as recorded in Euclidean Space and Real Matrices: Standing Notation (ii), we have $-Y=-(-X_{2})=X_{2}$ and hence $X\oplus(-Y)=X_{1}\oplus X_{2}$.

Step 4 (Claim 1). The first assertion of claim 1 is the statement about $X_{1}=X$ obtained in Step 3. For the second, apply claim 2 of Approximability by Test Data Under Negation with $v$ in place of $u$, the point $\hat{y}$, the vector $p$ and the matrix $Y$: it asserts that $\bigl(\hat{y},v(\hat{y}),p,Y\bigr)$ is approximable by test data from below for $v$ if and only if $\bigl(\hat{y},(-v)(\hat{y}),-p,-Y\bigr)$ is approximable by test data from above for $-v$. As $-Y=X_{2}$, the latter is exactly what Step 3 provides, so the former holds.

Step 5 (Claim 2). By The Doubling Matrix and its Elementary Properties (v) we have $\alpha J+\alpha^{-1}(\alpha J)^{2}=3\alpha J$, so the upper bound of Step 3 is the upper bound of claim 2.

For the lower bound, The Doubling Matrix and its Elementary Properties (v) gives $\lVert\alpha J\rVert\le 2\alpha$, whence $\alpha+\lVert\alpha J\rVert\le\alpha+2\alpha=3\alpha$. Let $z\in\mathbb{R}^{2n}$. By Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (vi),

$$z\cdot\bigl((-3\alpha I_{2n})z\bigr)=-3\alpha\lVert z\rVert^{2},\qquad z\cdot\Bigl(\bigl(-(\alpha+\lVert\alpha J\rVert)I_{2n}\bigr)z\Bigr)=-\bigl(\alpha+\lVert\alpha J\rVert\bigr)\lVert z\rVert^{2}.$$

Since $\lVert z\rVert^{2}$ is nonnegative by claim 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square and claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, multiplying $\alpha+\lVert\alpha J\rVert\le 3\alpha$ by $\lVert z\rVert^{2}$ and reversing signs with claim 4 of Elementary Order Arithmetic in an Ordered Field gives $-3\alpha\lVert z\rVert^{2}\le-\bigl(\alpha+\lVert\alpha J\rVert\bigr)\lVert z\rVert^{2}$. Hence $-3\alpha I_{2n}\preceq-\bigl(\alpha+\lVert\alpha J\rVert\bigr)I_{2n}$, and claim 2 follows from Step 3 by transitivity of $\preceq$.

Step 6 (Claim 3). Let $\xi,\eta\in\mathbb{R}^{n}$ and put $z=\iota(\xi,\eta)$. By Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix (ii), claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum and claim 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite,

$$z\cdot\Bigl(\bigl(X\oplus(-Y)\bigr)z\Bigr)=\xi\cdot(X\xi)+\eta\cdot\bigl((-Y)\eta\bigr)=\xi\cdot(X\xi)-\eta\cdot(Y\eta).$$

By Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (vi) and claim 3 of Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space,

$$z\cdot\bigl((-3\alpha I_{2n})z\bigr)=-3\alpha\lVert z\rVert^{2}=-3\alpha\bigl(\lVert\xi\rVert^{2}+\lVert\eta\rVert^{2}\bigr),$$

and by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, claim 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite and The Doubling Matrix and its Elementary Properties (ii), $z\cdot\bigl((3\alpha J)z\bigr)=3\alpha\lVert\xi-\eta\rVert^{2}$. Claim 3 is therefore claim 2 read through the description of $\preceq$ in Euclidean Space and Real Matrices: Standing Notation (iv), every point of $\mathbb{R}^{2n}$ being of the form $\iota(\xi,\eta)$.

Step 7 (Claim 4). Immediate from claim 2 and The Doubling Matrix and its Elementary Properties (vi), applied with $c=3\alpha$.

Step 8 (Claim 5). By claim 2 and The Doubling Matrix and its Elementary Properties (v), $X\oplus(-Y)\preceq 3\alpha J\preceq 6\alpha I_{2n}$. Also $-6\alpha I_{2n}\preceq-3\alpha I_{2n}$: for $z\in\mathbb{R}^{2n}$ the two quadratic forms are $-6\alpha\lVert z\rVert^{2}$ and $-3\alpha\lVert z\rVert^{2}$ by Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (vi), and $3\alpha\le 3\alpha+3\alpha=6\alpha$ because $0\le 3\alpha$, so multiplying by the nonnegative number $\lVert z\rVert^{2}$ and reversing signs with claim 4 of Elementary Order Arithmetic in an Ordered Field gives the asserted inequality of quadratic forms. By transitivity, $-6\alpha I_{2n}\preceq X\oplus(-Y)\preceq 6\alpha I_{2n}$, so claim 3 of Properties of the Norm of a Symmetric Real Matrix, applicable since $0\le 6\alpha$, gives $\lVert X\oplus(-Y)\rVert\le 6\alpha$.

By Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix (iii), $\lVert X\oplus(-Y)\rVert$ is the larger of $\lVert X\rVert$ and $\lVert-Y\rVert$, and $\lVert-Y\rVert=|-1|\,\lVert Y\rVert=\lVert Y\rVert$ by claim 5 of Properties of the Norm of a Symmetric Real Matrix, since $|-1|=1$ by claims 2 and 1 of Properties of the Absolute Value in an Ordered Field together with claims 6 and 4 of Elementary Order Arithmetic in an Ordered Field. Hence $\lVert X\rVert\le 6\alpha$ and $\lVert Y\rVert\le 6\alpha$.