On the algorithm of best approximation
by low rank matrices in the Chebyshev norm.111) This work was supported by
Russian Science Foundation (project 21-71-10072).)

S. Morozov1∗, N. Zamarashkin1∗∗, E. Tyrtyshnikov1∗∗∗
1 Marchuk Institute of Numerical Mathematics of the Russian Academy of
Sciences
e–mail<EMAIL_ADDRESS>
e–mail<EMAIL_ADDRESS>
e–mail<EMAIL_ADDRESS>
The low-rank matrix approximation problem is ubiquitous in computational
mathematics. Traditionally, this problem is solved in spectral or Frobenius
norms, where the accuracy of the approximation is related to the rate of
decrease of the singular values of the matrix. However, recent results
indicate that this requirement is not necessary for other norms. In this
paper, we propose a method for solving the low-rank approximation problem in
the Chebyshev norm, which is capable of efficiently constructing accurate
approximations for matrices, whose singular values do not decrease or decrease
slowly.

Keywords: Low-rank matrix approximation, Remez algorithm, Chebyshev
approximation.

1\. INTRODUCTION

Low-rank matrices are ubiquitous in science. They serve as a tool for low-
parametric matrix approximation in numerous applications such as computational
mathematics [1], computational fluid dynamics [6], recommender systems [3],
machine learning [8], and others.

However, one typically assumes that the singular values of the matrix that
needs to be approximated decay rapidly. This assumption is made, primarily,
because there are efficient algorithms for close-to-optimal low-rank
approximation in unitarily invariant norms [2, 4, 5].

On the other hand, in modern applications, especially in the field of big
data, it is often more natural to use other matrix norms. For example, in the
classical scheme of recommender systems, one deals with rating matrices, the
rows of which correspond to products (films, music, etc.) and the columns
correspond to users. The values of the matrix entries determine the ratings
given to products by users. To restore the missing ratings and provide
recommendations, a low-rank approximation of the matrix is constructed based
on the known elements. In this case, it seems more natural to approximate the
matrix elementwise, rather than in spectral or Frobenius norms: try to
approximate the values of all ratings in the best possible way. Moreover, as
follows from the article [7], statistical models used to describe the rating
matrices lead, in general, to matrices with a slow decay of singular values,
but which can be approximated elementwise with matrices of low rank. The
latter means that the use of low-rank approximation algorithms based on
singular value decompositions in recommender systems can hardly be considered
reasonable.

We consider the best low-rank appromation problem in the so-called Chebyshev
norm:

$\|X\|_{C}=\max\limits_{i,j}|x_{ij}|.$

Namely, for given matrix $A\in\mathbb{C}^{m\times n}$ and integer $r$, it is
required to find $U\in\mathbb{C}^{m\times r}$ and $V\in\mathbb{C}^{n\times r}$
such that

$\mu=\inf\limits_{U\in\mathbb{C}^{m\times r},V\in\mathbb{C}^{n\times
r}}\left\|A-UV^{T}\right\|_{C}.$ (1)

Matrices $\widehat{U}$ and $\widehat{V}$ satisfying

$\left\|A-\widehat{U}\widehat{V}^{T}\right\|_{C}=\mu,$

will be called matrices of best approximation of $A$ of rank $r$.

As natural as problem (1) is, to date, it has been little studied: there are
asymptotic estimates for the accuracy of the approximation (1) [7] and a
method for constructing local minima of the problem (1) in the case of rank 1
[9].

In this paper, we propose and justify an algorithm for solving the problem

$\mu=\inf\limits_{U\in\mathbb{R}^{m\times r}}\left\|A-UV^{T}\right\|_{C}$

for an arbitrary rank. Based on this algorithm, we develop a method of finding
local minima of the problem (1) for an arbitrary rank. A large number of
numerical experiments show that the asymptotic estimates proved in [7] are
generally not optimal.

The rest of the paper is organized as follows. In Section 2, we collect the
known results from the literature about the problem we consider. Section 3
presents basic results on the properties of the solution, including the
questions of the existence, uniqueness, and continuity of the solution. In
addition, we discuss the question of existence of characteristic sets and
their properties, together with the well-known results on how to solve the
problem for $(r+1)\times r$ matrices. We also consider the optimality criteria
of solutions. In Section 4, we present a combinatorial formula for solving the
problem and propose a generalized Remez algorithm, which makes it possible to
find solutions, in practice, in a polynomial number of operations. Section 5
gives an algorithm for solving the problem in the case when both matrices $U$
and $V$ are assumed to be unknown. Numerical experiments from Section 6
demonstrate the effectiveness of the proposed method, and also lead to a
number of new questions about the asymptotic accuracy of approximations of
matrices in the Chebyshev norm. Section 7 concludes the paper.

2\. EXISTING RESULTS

As far as we know, the problem of constructing and analyzing low-rank
approximations of matrices in the Chebyshev norm has been little studied. We
rely on two works [7, 9]. The first of them contains results on the asymptotic
properties of Chebyshev approximations of matrices (without the assumption
that singular values decrease), and the second contains a method for finding
local optima for the problem (1) for rank $1$.

Let us take a closer look at these works. One of the results proven in [7] is
the following general statement.

######  Theorem 1.

Let $X\in\mathbb{R}^{m\times n}$, where $m\geq n$ and $0<\varepsilon<1$. Then,
with

$r=\lceil 72\log{(2n+1)}/\varepsilon^{2}\rceil$

we have

$\inf\limits_{\operatorname{rank}Y\leq r}\|X-Y\|_{C}\leq\varepsilon\|X\|_{2}.$

It is clear from this theorem that Chebyshev low-rank approximations have
great potential. So for any sequence of matrices with bounded spectral norms,
for a fixed accuracy $\varepsilon$, the rank of the Chebyshev approximation
grows at most logarithmically. For example, for the best rank$-(n-1)$
approximation of the $n\times n$ identity matrix in the spectral or Frobenius
norms, its accuracy is $1$. At the same time, in the Chebyshev norm, the
identity matrix can be approximated with any fixed accuracy $\varepsilon>0$
with rank that is logarithmic in the order of the matrix $n$. In [7], this
property of the Chebyshev norm is called one of the main reasons why matrices
arising in data analysis can be efficiently approximated by low-rank matrices.

As far as we know, the only paper that studies the problem (1) is [9], where
rank-$1$ approximation is considered. First, in [9], the problem of the form

$\mu=\inf\limits_{u\in\mathbb{R}^{m}}\left\|A-uv^{T}\right\|_{C}.$ (2)

is solved. It is easy to see that for each row of the matrix $A$ the problem
(2) can be solved independently and, therefore, is reduced to

$\mu=\inf\limits_{u\in\mathbb{R}}\left\|a-uv\right\|_{\infty}.$

This implies a simple algorithm for solving the problem (2). In order to
obtain the local minimum of the solution to the problem (1), the authors use
the alternance method. Let an initial vector $v^{(0)}$ be given. Solving the
problem (2) for fixed $v=v^{(0)}$, we find a solution $u^{(1)}$. Further, for
fixed $u=u^{(1)}$, we solve the problem

$\mu=\inf\limits_{v\in\mathbb{R}^{n}}\left\|A-uv^{T}\right\|_{C}$

and find a solution $v^{(1)}$. Continuing according to this scheme, we come to
a solution, which, however, is not always a global optimum to the problem (1).
In addition, [9] contains a necessary condition for the optimality of the
solution $u,v$ of the problem (1) for rank 1. For simplicity, we assume that
all elements $u$ and $v$ are nonzero.

######  Statement 1.

Let all elements of the vectors $u$ and $v$ be nonzero and assume that they
are a solution to the problem (1). Let $R=A-uv^{T}$. Then in the matrix $R$
there is a cycle, that is, a set of indices
$(i_{1},j_{1}),(i_{1},j_{2}),(i_{2},j_{2}),\dots,(i_{k},j_{k}),(i_{k},j_{1})$
such that

  1. 1.

indices $i_{1},\dots,i_{k}$ are distinct;

  2. 2.

indices $j_{1},\dots,j_{k}$ are distinct;

  3. 3.

at each of these positions in the matrix $R$, the maximum absolute value is
reached;

  4. 4.

let $(i_{t},j_{p})$ and $(i_{g},j_{h})$ be adjacent in the cycle, that is,
they are different pairs of indices such that $t=g$ or $p=h$. Then the signs
of the values $u_{i_{t}}v_{j_{p}}r_{i_{t}j_{p}}$ and
$u_{i_{g}}v_{j_{h}}r_{i_{g}j_{h}}$ are distinct.

In what follows, we prove generalizations of these results to the case of
arbitrary rank.

3\. PRELIMINARIES

Now, we are going to provide several basic results that will be useful to us.
A significant part of them is a reformulation of the well-known results from
the theory of Chebyshev approximations of functions for the matrix case [10,
12]. In this section, we are interested in the following problem

$\mu=\inf\limits_{U\in\mathbb{C}^{m\times r}}\left\|A-UV^{T}\right\|_{C}.$ (3)

Matrix $\widehat{U}$ satisfying

$\left\|A-\widehat{U}V^{T}\right\|_{C}=\mu,$

is called a matrix of the best approximation $A$ with respect to the system of
vectors $V$. The task is to find a matrix $\widehat{U}\in\mathbb{C}^{m\times
r}$ of the best approximation. It is easy to understand that this problem is
divided into $m$ independent subproblems for each row of the matrix $A$, for
which it is required to find the corresponding row of the matrix
$\widehat{U}$. Therefore, we are going to solve the following problem. Let the
matrix $V\in\mathbb{C}^{n\times r}$ and the vector $a\in\mathbb{C}^{n}$ be
given. It is required to find

$\mu=\inf\limits_{u\in\mathbb{C}^{r}}\left\|a-Vu\right\|_{\infty}$ (4)

and vector $\widehat{u}\in\mathbb{C}^{r}$ satisfying

$\left\|a-V\widehat{u}\right\|_{\infty}=\mu.$

3.1. Existence, uniqueness, continuity

Let us present the results on the existence, uniqueness and continuity of the
solution to the problem (4). The existence of a solution, that is, the
existence of such $\widehat{u}\in\mathbb{C}^{r}$ that

$\left\|a-V\widehat{u}\right\|_{\infty}=\mu$

is obvious. Consider the question of the uniqueness of the solution. In what
follows, we will denote columns of matrices by subscripts and rows by
superscripts. Let us introduce the concept of a Chebyshev vector system.

Definition 1. The columns of the matrix $V\in\mathbb{C}^{n\times r}$ form a
Chebyshev system of vectors if any $r$ rows of the matrix $V$ are linearly
independent.

This concept is closely related to the uniqueness of the solution to the
problem of best approximation. Namely, we have the following

######  Theorem 2.

(Haar [10]). Let the matrix $V\in\mathbb{C}^{n\times r}$ and $n>r$ be given.
Then, for any vector $a\in\mathbb{C}^{n}$ the solution is unique if and only
if the columns of the matrix $V$ form a Chebyshev system.

The following statement is also true

######  Statement 2.

Let the columns of the matrix $V\in\mathbb{C}^{n\times r}$, where $n>r$ form a
Chebyshev system and let $V\widehat{u}$ be the vector of the best
approximation. Then the maximum absolute value is reached at least at $r+1$
points, that is, there are $i_{1},\dots,i_{r+1}$ which satisfy the equality

$|a_{i_{j}}-(V\widehat{u})_{i_{j}}|=\|a-V\widehat{u}\|_{\infty},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,r+1.$

###### Proof.

Let the number of points at which the maximum absolute value is reached be
equal to $r_{1}<r+1$. Then, having solved the system with $r_{1}$ equations
and $r$ unknowns, whose rows are linearly independent, we can obtain a vector
$p\in\mathbb{C}^{r}$ such that

$(Vp)_{i_{j}}=a_{i_{j}}-(V\widehat{u})_{i_{j}},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,r_{1}.$

But then the vector $V(\widehat{u}+\delta p)$ for a sufficiently small
$\delta$ deviates from $a$ less than $V\widehat{u}$. We come to a
contradiction. ∎

Consider the issue of continuity of the solution.

######  Theorem 3.

(Nikolsky [10]). Let the system of columns of the matrix
$V\in\mathbb{C}^{n\times r}$, where $n>r$, form a Chebyshev system. Then the
coefficients of the best approximation vector $\widehat{u}$ continuously
depend on the approximated vector $a$, and the column system $V$, that is,
$\forall\varepsilon>0$ $\exists\delta=\delta(a,V,\varepsilon)>0$ such that if
$\|a-b\|_{\infty}+\|V-W\|<\delta$, then
$\|\widehat{u}(a,V)-\widehat{u}(b,W)\|_{\infty}<\varepsilon$, where
$\widehat{u}(a,V)$ and $\widehat{u}(b,W)$ denote the coefficients of the
optimal solution for the vectors $a$ and $b$ by the systems $V$ and $W$,
respectively.

3.2. Characteristic sets

Let $J$ denote the set of indices $J=\left\\{1,2,\dots,n\right\\},$ and let
$J^{\prime}$ and $J^{\prime\prime}$ be subsets of $J$. Denote

$\mu(J^{\prime})=\inf\limits_{u\in\mathbb{C}^{r}}\left\|a(J^{\prime})-V(J^{\prime})u\right\|_{\infty},$

where $V(J^{\prime})$ denotes the submatrix of the matrix $V$ containing rows
with numbers from the set $J^{\prime}$, and $a(J^{\prime})$ denotes the
subvector of the vector $a$ containing elements with the indices from
$J^{\prime}$.

Definition 2. A set $J^{\prime}$ is called a characteristic set if
$\mu(J)=\mu(J^{\prime})$ and for any subset $J^{\prime\prime}\subsetneq
J^{\prime}$, $\mu(J^{\prime\prime})<\mu(J)$.

Further, we will show that if the columns of $V$ are linearly independent,
then there is at least one characteristic set containing at most $2r+1$ points
in the complex case and at most $r+1$ points in the real case.

We need the following notation [10, 12]. Let $\lambda\geq 0$. Denote

$\displaystyle F(j,u)$ $\displaystyle=$
$\displaystyle\left|a_{j}-u^{T}v^{j}\right|,$ $\displaystyle K(j,\lambda)$
$\displaystyle=$
$\displaystyle\left\\{u\in\mathbb{C}^{r}|F(j,u)\leq\lambda\right\\},$
$\displaystyle K(J^{\prime},\lambda)$ $\displaystyle=$
$\displaystyle\bigcap\limits_{j\in
J^{\prime}}K(j,\lambda)=\left\\{u\in\mathbb{C}^{r}|F(j,u)\leq\lambda,\forall
j\in J^{\prime}\right\\}.$

It is easy to see that the following is true.

######  Statement 3.

$\displaystyle K(j,\lambda^{\prime})$ $\displaystyle\subset$ $\displaystyle
K(j,\lambda^{\prime\prime}),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ K(J^{\prime},\lambda^{\prime})\subset
K(J^{\prime},\lambda^{\prime\prime}),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ 0\leq\lambda^{\prime}<\lambda^{\prime\prime},$
$\displaystyle K(J^{\prime\prime},\lambda)$ $\displaystyle\subset$
$\displaystyle K(J^{\prime},\lambda),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ J^{\prime}\subset J^{\prime\prime}.$

######  Lemma 1.

Let the columns of the matrix $V$ be linearly independent. Then the set
$K(j,\lambda)$ is convex and closed, and the set $K(J,\lambda)$ is bounded for
any $\lambda\geq 0$.

###### Proof.

Let us prove that the sets $K(j,\lambda)$ are closed. Let $u_{1}$ be the limit
point of the set $K(j,\lambda)$. Then in any of its neighborhood there are
points $u\in K(j,\lambda)$.

$F(j,u_{1})\leq|F(j,u_{1})-F(j,u)|+F(j,u)$

Since $u\in K(j,\lambda)$, then $F(j,u)\leq\lambda$. The function

$F(j,u)=\left|a_{j}-u^{T}v^{j}\right|$

is continuous in $u$ for any fixed $j$. Then for any $\varepsilon>0$ there is
$\delta>0$ such that if $|u-u_{1}|<\delta$, then
$|F(j,u_{1})-F(j,u)|<\varepsilon$. Thus, we have

$F(j,u_{1})<\varepsilon+\lambda$

for any $\varepsilon>0$, hence $u_{1}\in K(j,\lambda)$. The closedness is
proved.

Let us prove that $K(J,\lambda)$ is bounded. Consider the vector $Vu$ for
$\|u\|_{1}=1$. The quantity $\|Vu\|_{\infty}$ is a function continuous in $u$
on a compact set; therefore, at some point it reaches its minimum value

$M=\|V\widehat{u}\|_{\infty}\leq\|Vu\|_{\infty}.$

Since the columns $V$ are linearly independent, any non-trivial linear
combination of them is not equal to $0$ and $M>0$.

Let $\|u\|_{1}\geq\dfrac{C+1}{M}$, where $C>0$ is a constant. Then

$\|a-Vu\|_{\infty}\geq\|Vu\|_{\infty}-\|a\|_{\infty}\geq\|u\|_{1}M-\|a\|_{\infty}\geq
C+1-\|a\|_{\infty}.$

Then for $\|u\|_{1}\geq\dfrac{C+1}{M}$ the condition
$F(J,u)\leq\lambda=C-\|a\|_{\infty}$ cannot be satisfied, that is $u\notin
K(j,\lambda)$ for $\lambda\leq C-\|a\|_{\infty}$. Since $C$ is arbitrary, the
boundedness is proved.

Let us prove the convexity of the set $K(j,\lambda)$. Let $u_{1},u_{2}\in
K(j,\lambda)$, that is $F(j,u_{1})\leq\lambda$ and $F(j,u_{2})\leq\lambda$. We
need to prove that $F(j,\tau u_{1}+(1-\tau)u_{2})\leq\lambda$ for any
$\tau\in(0,1)$.

$\displaystyle F(j,\tau u_{1}+(1-\tau)u_{2})$ $\displaystyle=$
$\displaystyle|a_{j}-(\tau u_{1}+(1-\tau)u_{2})^{T}v^{j}|$ $\displaystyle=$
$\displaystyle|\tau(a_{j}-u_{1}^{T}v^{j})+(1-\tau)(a_{j}-u_{2}^{T}v^{j})|$
$\displaystyle\leq$ $\displaystyle\tau
F(j,u_{1})+(1-\tau)F(j,u_{2})\leq\lambda.$

∎

We denote by $M_{k}$ the set of all ordered subsets $J_{k}$, consisting of $k$
elements $i_{1},\dots,i_{k}$, taken from the set $J$. We denote by
$\mu_{k}(J)$ the exact upper bound of the least deviations from zero of the
function $F(j,u)$ on all subsets of $J_{k}\in M_{k}$:

$\mu_{k}(J)=\max\limits_{J_{k}\in M_{k}}\mu(J_{k})=\max\limits_{J_{k}\in
M_{k}}\min\limits_{u\in\mathbb{C}^{r}}\max\limits_{j\in J_{k}}F(j,u).$

It is easy to prove the following

######  Statement 4.

$\mu_{k}(J)\leq\mu_{k+1}(J)\leq\mu(J),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall k$.

For further analysis, we need the following theorem

######  Theorem 4.

(Helly). If the collection $K$ of closed convex sets of points
$x\in\mathbb{R}^{r}$ contains at least $r+1$ sets (some of which may be the
same), the intersection of any $r+1$ sets from $K$ is not empty and the
intersection of a finite number of sets from $K$ is bounded, then the
intersection of all sets from $K$ is not empty.

Based on Helly’s theorem, let us prove the following result.

######  Theorem 5.

(Shnirelman [10]). If there is a $\lambda_{0}>\mu_{2r+1}$
($\lambda_{0}>\mu_{r+1}$ in real case), such that for any $j$ and any
$\lambda$, $\mu_{2r+1}<\lambda<\lambda_{0}$ ($\mu_{r+1}<\lambda<\lambda_{0}$
in real case), the sets $K(j,\lambda)$ are closed and convex and the
intersection of a finite number of sets $K(j,\lambda)$ is bounded, then
$\mu_{2r+1}(J)=\mu(J)$ ($\mu_{r+1}(J)=\mu(J)$ in real case).

###### Proof.

Let $k=r+1$ in the real case and $k=2r+1$ in the complex case. Since the sets
$J_{k}$ and $M_{k}$ are finite, we have that the maxima and minima are
attained, therefore, for any $\lambda>\mu_{k}(J)$, the set $K(J_{k},\lambda)$
is not empty. Moreover, since $K(j,\lambda)$ are convex and closed, then

$K(J_{k},\lambda)=\bigcap\limits_{j\in J_{k}}K(j,\lambda)$

is nonempty and convex for any $J_{k}\in M_{k}$.

Let us verify that all conditions of Helly’s theorem are satisfied. As the
collection of sets $K$ we take the sets $K(j,\ lambda)$, $j\ inJ$. By the
hypothesis of the theorem, they are closed and convex, and the intersection of
some finite number of these sets is bounded. In the real case, the fact that
the intersection of any $j+1$ sets is not empty is equivalent to the fact that
$K(J_{r+1},\lambda)$ is not empty, as shown above. In the complex case, we
need to work with the space $\mathbb{C}^{r}$, which we identify with
$\mathbb{R}^{2r}$, so we need the intersection of any $2r+1$ sets to be non-
empty , which was also shown above. So, all conditions of Helly’s theorem are
satisfied and we have that

$K(J,\lambda)=\bigcap\limits_{j\in J}K(j,\lambda)$

is nonempty, convex and bounded.

Assume that the sequence $\\{\lambda_{t}\\}$ decreases,
$\mu_{k}<\lambda_{t}<\lambda_{0}$ and it tends to $\mu_{k}$. Moreover, let
$K(J,\lambda_{t+1})\subset K(J,\lambda_{t})$ and the intersection

$K=\bigcap\limits_{t=1}^{\infty}K(J,\lambda_{t})$

be nonempty, convex and bounded. Let $u_{0}\in K$. This means that $u_{0}\in
K(J,\lambda_{t})$, hence $F(j,u_{0})\leq\lambda_{t}$ for any $j\in J$ and any
$t$. In the limit as $t\to\infty$, we see that $F(j,u_{0})\ le\mu_{k}(J)$ for
any $j\in J$, whence

$\mu(J)\leq\max\limits_{j\in J}F(j,u_{0})\leq\mu_{k}(J).$

But, as noted above, $\mu_{k}(J)\leq\mu(J)$. ∎

This theorem allows us to formulate the following result.

######  Theorem 6.

Let the columns of the matrix $V\in\mathbb{C}^{n\times r}$, where $n\geq r$,
be linearly independent and assume that the vector $a$ does not belong to the
range of the matrix $V$. Then there is at least one characteristic set
consisting of at most $2r+1$ points in the complex case and $r+1$ points in
the real one. Moreover, if the system of columns of the matrix $V$ is
Chebyshev, then any characteristic set consists of at least $r+1$ points.

###### Proof.

The result for an arbitrary system immediately follows from Lemma 1 and
Theorem 5. In the case of a Chebyshev system, on any set of $r$ or fewer
points, one can solve the system and precisely approximate the vector at these
points, and since the set is characteristic, this contradicts the condition
that $a$ does not belong to the range of $V$. ∎

3.3. On the problem of finding equidistant points

Let us introduce the concept of an equidistant point of the system

Definition 3. Let $V\in\mathbb{R}^{(r+1)\times r}$ and $a\in\mathbb{R}^{r+1}$.
Let the system

$Vu=a$

be inconsistent. A point $u$ is called an equidistant point of the system if

$\rho(u)=|(v^{1},u)-a_{1}|=|(v^{2},u)-a_{2}|=\dots=|(v^{r+1},u)-a_{r+1}|.$

A point $u$ is called the best equidistant point of the system if it is
equidistant and the value $\rho(u)$ is minimal.

Let us present the results [11] on the structure of the set of all equidistant
points of the system in the real case. Let

$\widehat{V}_{j}=\begin{bmatrix}v_{1}^{1}&v_{2}^{1}&\dots&v_{r}^{1}\\\
v_{1}^{2}&v_{2}^{2}&\dots&v_{r}^{2}\\\ \vdots&\vdots&\vdots&\vdots\\\
v_{1}^{j-1}&v_{2}^{j-1}&\dots&v_{r}^{j-1}\\\
v_{1}^{j+1}&v_{2}^{j+1}&\dots&v_{r}^{j+1}\\\ \vdots&\vdots&\vdots&\vdots\\\
v_{1}^{r+1}&v_{2}^{r+1}&\dots&v_{r}^{r+1}\\\ \end{bmatrix}$

and $\widehat{a}_{j}=(a_{1},a_{2},\dots,a_{j-1},a_{j+1},\dots,a_{r+1})^{T}$.
Then denote $D_{j}=\det\widehat{V}_{j}$ and let $\widehat{u}^{j}$ be the
solution of the system $\widehat{V}_{j}u=\widehat{a}_{j}$. The following
theorems about the set of equidistant points of the system hold.

######  Theorem 7.

(Dzyadyk [11]). Let an inconsistent system of equations $Vu=a$ be given, where
$V\in\mathbb{R}^{(r+1)\times r}$ and $a\in\mathbb{R}^{r+1}$. Then

  1. 1.

For each $j=1,\dots,r+1$ we have

$(v^{j},\widehat{u}^{j})-a_{j}=\dfrac{(-1)^{j+1}}{D_{j}}\sum\limits_{\nu=1}^{r+1}(-1)^{\nu}a_{\nu}D_{\nu}.$

  2. 2.

For any real $k_{j}$, $j=1,\dots,r+1$ such that

$\sum\limits_{j=1}^{n+1}|D_{j}|e^{ik_{j}}\neq 0$

point $u$ determined by the formula

$u=\rho\sum\limits_{j=1}^{r+1}\dfrac{\widehat{u}^{j}e^{ik_{j}}}{|(v^{j},\widehat{u}^{j})-a_{j}|}=\rho\dfrac{\sum\limits_{j=1}^{r+1}|D_{j}|\widehat{u}^{j}e^{ik_{j}}}{\left|\sum\limits_{j=1}^{r+1}(-1)^{j}D_{j}a_{j}\right|},$

where

$\rho=\left(\sum\limits_{j=1}^{r+1}\dfrac{e^{ik_{j}}}{|(v^{j},\widehat{u}^{j})-a_{j}|}\right)^{-1}=\dfrac{\left|\sum\limits_{j=1}^{r+1}(-1)^{j}D_{j}a_{j}\right|}{\sum\limits_{j=1}^{r+1}|D_{j}|e^{ik_{j}}}$

is an equidistant point of the system $Vu=a$, while $|\rho|$ is equal to the
$V$-distance from the point $u$ to $a$.

  3. 3.

Any equidistant point $u$ of the system $Vu=a$ can be represented for some
real $k_{j}$ by the formula above. In this case, $k_{j}$ can, in particular,
be expressed by the formula

$k_{j}=\arg((v^{j},u)-a_{j})-\arg((v^{j},\widehat{u}^{j})-a_{j}).$

######  Theorem 8.

(Dzyadyk [11]). Let an inconsistent system of equations $Vu=a$ be given, where
$V\in\mathbb{R}^{(r+1)\times r}$ and $a\in\mathbb{R}^{r+1}$. Then the best
equidistant point $u^{*}$ of the system $Vu=a$ can be determined by the
formula

$u^{*}=\rho^{*}\sum\limits_{j=1}^{r+1}\dfrac{\widehat{u}^{j}}{|(v^{j},\widehat{u}^{j})-a_{j}|}=\dfrac{\sum\limits_{j=1}^{r+1}|D_{j}|\widehat{u}^{j}}{\sum\limits_{j=1}^{r+1}|D_{j}|},$

where

$\rho^{*}=\left(\sum\limits_{j=1}^{r+1}\dfrac{1}{|(v^{j},\widehat{u}^{j})-a_{j}|}\right)^{-1}=\dfrac{\left|\sum\limits_{j=1}^{r+1}(-1)^{j}D_{j}a_{j}\right|}{\sum\limits_{j=1}^{r+1}|D_{j}|}.$

###### Proof.

It suffices to note that the value

$\rho=\left(\sum\limits_{j=1}^{r+1}\dfrac{e^{ik_{j}}}{|(v^{j},\widehat{u}^{j})-a_{j}|}\right)^{-1}$

takes the smallest value when all terms are coaligned, that is,
$e^{ik_{1}}=e^{ik_{2}}=\dots=e^{ik_{r+1}}$. ∎

3.4. Optimality criteria

Let us give several criteria for the optimality of the solution. These
criteria are interesting themselves, and allow one to get new important
information about the problem.

######  Theorem 9.

(Kolmogorov). Let a system of vectors with a matrix $V\in\mathbb{C}^{n\times
r}$ and a vector $a\in\mathbb{C}^{n}$ be given, so that vector $a$ should be
approximated by a linear combination of columns of $V$. For the vector
$V\widehat{u}$ to be the vector of the best approximation for $a$, it is
necessary and sufficient that on the set $E=E(V\widehat{u})$ of all points at
which for the vector $V\widehat{u}$ the maximum absolute value of the residual
is reached, for all vectors of the form $Vu$ the equality

$\min\limits_{j\in E}{\rm
Re\,}\left((Vu)_{j}\overline{\left(a_{j}-(V\widehat{u})_{j}\right)}\right)\leq
0.$

is satisfied.

###### Proof.

Necessity. Let $V\widehat{u}$ be the vector of best approximation for $a$. By
contradiction, let

$\min\limits_{j\in E}{\rm
Re\,}\left((Vu)_{j}\overline{\left(a_{j}-(V\widehat{u})_{j}\right)}\right)>c>0$

for some vector $u\in\mathbb{C}^{r}$. Denote

$G=\max\limits_{j\in E}|a_{j}-(V\widehat{u})_{j}|,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ G^{\prime}=\max\limits_{j\notin
E}|a_{j}-(V\widehat{u})_{j}|,$ $h=G-G^{\prime}>0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
M=\max\limits_{j}|(Vu)_{j}|,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\lambda=\max\left\\{\dfrac{c}{M^{2}},\dfrac{h}{2M}\right\\}>0.$

Let us prove then that the vector $V(\widehat{u}+\lambda u)$ approximates the
vector $a$ better.

1) Let $j\in E$. Then

$\displaystyle|a_{j}-(\widehat{u}+\lambda u)^{T}v^{j}|^{2}$ $\displaystyle=$
$\displaystyle(a_{j}-\widehat{u}^{T}v^{j}-\lambda
u^{T}v^{j})\cdot(\overline{(a_{j}-\widehat{u}^{T}v^{j})}-\lambda\overline{(u^{T}v^{j})})$
$\displaystyle=$
$\displaystyle|a_{j}-\widehat{u}^{T}v^{j}|^{2}+\lambda^{2}|u^{T}v^{j}|^{2}-2\lambda{\rm
Re\,}\left((Vu)_{j}\overline{\left(a_{j}-(V\widehat{u})_{j}\right)}\right)$
$\displaystyle\leq$ $\displaystyle G^{2}+\lambda^{2}M^{2}-2\lambda{\rm
Re\,}\left((Vu)_{j}\overline{\left(a_{j}-(V\widehat{u})_{j}\right)}\right)$
$\displaystyle<$ $\displaystyle G^{2}+\lambda^{2}M^{2}-2\lambda c\leq
G^{2}+\lambda\dfrac{c}{M^{2}}M^{2}-2\lambda c$ $\displaystyle=$ $\displaystyle
G^{2}-\lambda c<G^{2}.$

2) Let $j\notin E$. Then

$|a_{j}-(\widehat{u}+\lambda
u)^{T}v^{j}|\leq|a_{j}-\widehat{u}^{T}v^{j}|+\lambda|u^{T}v^{j}|\leq
G^{\prime}+\lambda M\leq G-h+\dfrac{h}{2M}M=G-h/2<G.$

It follows that the vector $V(\widehat{u}+\lambda u)$ approximates the vector
$a$ better. We get a contradiction.

Sufficiency. Let the condition of the Kolmogorov criterion be satisfied with
the vector of coefficients $\widehat{u}$ and let $u\in\mathbb{C}^{r}$ be
arbitrary. Consider the vector $w=V(u-\widehat{u})$. Let us choose the index
$j_{0}$ for which the inequality

${\rm
Re\,}\left((V(u-\widehat{u}))_{j_{0}}\overline{\left(a_{j_{0}}-(V\widehat{u})_{j_{0}}\right)}\right)\leq
0$

holds. Then

$\displaystyle|a_{j_{0}}-(Vu)_{j_{0}}|^{2}$ $\displaystyle=$
$\displaystyle|a_{j_{0}}-(V\widehat{u})_{j_{0}}-((Vu)_{j_{0}}-(V\widehat{u})_{j_{0}})|^{2}$
$\displaystyle=$
$\displaystyle|a_{j_{0}}-(V\widehat{u})_{j_{0}}|^{2}+|(Vu)_{j_{0}}-(V\widehat{u})_{j_{0}}|^{2}-2{\rm
Re\,}\left((V(u-\widehat{u}))_{j_{0}}\overline{\left(a_{j_{0}}-(V\widehat{u})_{j_{0}}\right)}\right)$
$\displaystyle\geq$ $\displaystyle|a_{j_{0}}-(V\widehat{u})_{j_{0}}|^{2}.$

This shows that for any vector $u\in\mathbb{C}^{r}$, the approximation given
by the vector $\widehat{u}$ is not worse; that is, it is optimal. ∎

Let us give another, in some situations more convenient, optimality criterion.
In a sense, it is a reformulation of the Kolmogorov criterion using the
following lemma.

######  Lemma 2.

Let $u_{ij}$, $i=1,\dots,m$, $j=1,\dots,n$ be some numbers. Then the numbers
$\delta_{i}\geq 0$, $i=1,\dots,m$ that are not all zero and such that

$\sum\limits_{i=1}^{m}\delta_{i}u_{ij}=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,n,$

exist if and only if for any system of numbers $c_{j}$, $j=1,\dots,n$,
inequalities

${\rm Re\,}\sum\limits_{j=1}^{n}c_{j}u_{ij}>0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ i=1,\dots,m,$

are not satisfied simultaneously.

###### Proof.

Necessity. Assume that for some $\delta_{i}\geq 0$, $i=1,\dots,m$

$\sum\limits_{i=1}^{m}\delta_{i}u_{ij}=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,n.$

Then

$\sum\limits_{i=1}^{m}\delta_{i}{\rm
Re\,}\sum\limits_{j=1}^{n}c_{j}u_{ij}={\rm
Re\,}\sum\limits_{j=1}^{n}c_{j}\sum\limits_{i=1}^{m}\delta_{i}u_{ij}=0,$

whence it follows that for any system $c_{j}$ the conditions

${\rm Re\,}\sum\limits_{j=1}^{n}c_{j}u_{ij}>0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ i=1,\dots,m,$

cannot be satisfied simultaneously.

Sufficiency. Introduce the function

$v=v(\delta_{1},\dots,\delta_{m})=\sum\limits_{j=1}^{n}\left|\sum\limits_{i=1}^{m}\delta_{i}u_{ij}\right|,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \delta_{i}\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum\limits_{i=1}^{m}\delta_{i}=1.$

Since the function $v$ is continuous on a compact set, it attains the minimum
value $v_{0}$ for $\delta_{i}=\delta_{i}^{0}$. Let us show that the condition
of the lemma is equivalent to the following: if the inequalities ${\rm
Re\,}\sum\limits_{j=1}^{n}c_{j}u_{ij}>0$ cannot be satisfied simultaneously,
then $v_{0}=0$.

Let us prove it by contradiction. Let the inequalities be satisfied
simultaneously for any $c_{j}$, but $v_{0}>0$. Take

$c_{j}=\sum\limits_{i=1}^{m}\delta_{i}^{0}\overline{u}_{ij}$

and assume that for such $c_{j}$, without loss of generality, the inequality
does not hold for $i=m$

${\rm
Re\,}\sum\limits_{j=1}^{n}\left(\sum\limits_{i=1}^{m}\delta_{i}^{0}\overline{u}_{ij}\right)u_{mj}\leq
0.$

Denote

$v_{*}=\sum\limits_{j=1}^{m}|u_{mj}|^{2},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\lambda=\dfrac{v_{*}}{v_{*}+v_{0}}<1.$

Let us choose $\delta_{i}$ as

$\delta_{i}=\begin{cases}\lambda\delta_{i}^{0},&i=1,2,\dots,m-1,\\\
(1-\lambda)+\lambda\delta_{m}^{0},&i=m,\\\ \end{cases}$

and show that $v(\delta_{1},\dots,\delta_{m})<v_{0}$. Indeed,

$\displaystyle v$ $\displaystyle=$
$\displaystyle\sum\limits_{j=1}^{n}\left|\sum\limits_{i=1}^{m}\delta_{i}u_{ij}\right|=\sum\limits_{j=1}^{n}\left|(1-\lambda)u_{mj}+\lambda\sum\limits_{i=1}^{m}\delta_{i}^{0}u_{ij}\right|$
$\displaystyle=$
$\displaystyle(1-\lambda)^{2}\sum\limits_{j}^{n}|u_{mj}|^{2}+\lambda^{2}\sum\limits_{j=1}^{n}\left|\sum\limits_{i=1}^{m}\delta_{i}^{0}u_{ij}\right|+2\lambda(1-\lambda){\rm
Re\,}\left(\sum\limits_{j=1}^{n}\sum\limits_{i=1}^{m}\delta_{i}^{0}\overline{u}_{ij}u_{mj}\right).$

As noted above,

${\rm
Re\,}\left(\sum\limits_{j=1}^{n}\sum\limits_{i=1}^{m}\delta_{i}^{0}\overline{u}_{ij}u_{mj}\right)\leq
0,$

but $\lambda\geq 0$, $1-\lambda>0$, whence

$v\leq(1-\lambda)^{2}v_{*}+\lambda^{2}v_{0}=\dfrac{v_{0}^{2}}{(v_{*}+v_{0})^{2}}v_{*}+\dfrac{v_{*}^{2}}{(v_{*}+v_{0})^{2}}v_{0}=v_{0}v_{*}\dfrac{v_{*}+v_{0}}{(v_{*}+v_{0})^{2}}=\dfrac{v_{*}}{v_{*}+v_{0}}v_{0}=\lambda
v_{0}<v_{0}.$

We come to a contradiction with the optimality of $v_{0}$, hence $v_{0}=0$. ∎

Note 1. If all $u_{ij}\in\mathbb{R}$, then it is sufficient to choose $c_{j}$
real.

Using this lemma and Kolmogorov’s criterion, we prove another optimality
criterion.

######  Theorem 10.

(Remez). Let a system of vectors with a matrix $V\in\mathbb{C}^{n\times r}$
and a vector $a\in\mathbb{C}^{n}$ be given, so that vector $a$ should be
approximated by a linear combination of columns of $V$. Let the vector
$V\widehat{u}$ attain the maximum absolute values of the residual in the
positions $E=\\{i_{1},\dots,i_{t}\\}$. Then $V\widehat{u}$ is the vector of
the best approximation for $a$ if and only if there are $\delta_{k}\geq 0$,
$k=1,\dots,t$, not all of which are equal zero, such that

$\sum\limits_{k\in
E}\delta_{k}\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}v_{j}^{k}=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,r.$

###### Proof.

Sufficiency. Let the conditions

$\sum\limits_{k\in
E}\delta_{k}\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}v_{j}^{k}=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,r.$

hold. Denote
$u_{ij}=\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}v_{j}^{k}$ as in the
previous lemma. Then, according to the lemma, the conditions

${\rm Re\,}\sum\limits_{j\in
E}c_{j}v_{j}^{k}\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}>0$

are not fulfilled simultaneously for all $c_{j}$. Taking into account that
$\sum\limits_{j\in E}c_{j}v_{j}^{k}$ defines an arbitrary vector of the form
$Vc$, we get that the Kolmogorov criterion is fulfilled and $V\widehat{u}$ is
the optimal approximation.

Necessity. If $V\widehat{u}$ is optimal, then Kolmogorov’s criterion is
fulfilled

$\min\limits_{k\in E}{\rm Re\,}\sum\limits_{j\in
E}c_{j}v_{j}^{k}\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}\leq 0,$

hence,

${\rm Re\,}\sum\limits_{j\in
E}c_{j}v_{j}^{k}\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}>0$

are not fulfilled simultaneously, and then by the lemma there are
$\delta_{k}\geq 0$ satisfying the Remez conditions. ∎

Note 2. There is always an optimal solution in which the maximum values are
attained at $t$ points, where $1\leq t\leq 2r+1$ in the complex case and
$1\leq t\leq r+1$ in the real case, and the condition of the Remez criterion
is satisfied with $\delta_{k}>0$.

Note 3. Note that the Remez condition can be rewritten as

$\sum\limits_{k\in
E}\delta_{k}\operatorname*{sign}\left\\{\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}\right\\}v_{j}^{k}=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,r.$

Suppose we somehow found the set $E$. Then using the Remez criterion it is
easy to find a solution. Let us solve the system

$\sum\limits_{k\in E}v_{j}^{k}s_{k}=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ j=1,\dots,r,$

This is a system with $r+1$ variables and $r$ equations, which has a non-
trivial solution. Let us find this solution. Then

$\delta_{k}=|s_{k}|,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\operatorname*{sign}\left\\{\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}\right\\}=\operatorname*{sign}s_{k}.$
(5)

Since Chebyshev system always has a characteristic set consisting exactly of
$r+1$ elements, for Chebyshev system with $r+1$ equations and $r$ unknowns,
the equation (5) gives the signs of the quantities
$\overline{\left(a_{k}-\widehat{u}^{T}v^{k}\right)}$ for the best equidistant
point. In addition, the absolute values of
$\left|a_{k}-\widehat{u}^{T}v^{k}\right|$ are equal, which allows in the real
case to write out a system with $r$ equations and $r$ unknowns, the solution
of which is the best equidistant point. Thus, the best equidistant point of
the Chebyshev system of size $(r+1)\times r$ can be found for $O(r^{3})$
operations by solving a system of linear equations twice.

4\. ON THE PROBLEM OF FINDING CHARACTERISTIC SETS IN THE REAL CASE

Let us move on to the methods for solving the problem (4).

4.1. Combinatorial solution formula

Suppose we need to solve the problem of approximating the vector
$a\in\mathbb{R}^{n}$ by the system of vectors $V\in\mathbb{R}^{n\times r}$.
Let $\widetilde{V}\in\mathbb{R}^{(r+1)\times r}$ and
$\widetilde{a}\in\mathbb{R}^{r+1}$. Then we denote by
$\begin{bmatrix}\widetilde{V}&\widetilde{a}\end{bmatrix}\in\mathbb{R}^{(r+1)\times(r+1)}$
the matrix whose first $r$ columns are columns of the matrix $\widetilde{V}$,
and the last column is $\widetilde{a}$. Denote by $V(i_{1},\dots,i_{k})$ the
submatrix of the matrix $V$ containing the rows $i_{1},\dots,i_{k}$.
Similarly, we denote by $a(i_{1},\dots,i_{k})$ the subvector of the vector $a$
containing elements $i_{1},\dots,i_{k}$. In addition, we denote by
$\widetilde{V}_{\setminus k}$ the submatrix of the matrix $\widetilde{V}$, in
which the $k$-th row is deleted.

######  Theorem 11.

Suppose we need to solve the problem of approximating the vector
$a\in\mathbb{R}^{n}$ by the system of vectors $V\in\mathbb{R}^{n\times r}$.
Let

$\mu=\inf\limits_{u\in\mathbb{R}^{r}}\left\|a-Vu\right\|_{\infty}.$

Then

$\mu=\max\limits_{i_{1},i_{2},\dots,i_{r+1}}\dfrac{\left|\det\begin{bmatrix}V(i_{1},i_{2},\dots,i_{r+1})&a(i_{1},i_{2},\dots,i_{r+1})\end{bmatrix}\right|}{\sum\limits_{k=1}^{r+1}\left|\det\left(V(i_{1},i_{2},\dots,i_{r+1})_{\setminus
k}\right)\right|}.$

###### Proof.

By the Theorem 5 we have that

$\mu(J)=\mu_{r+1}(J),$

and according to the definition

$\mu_{r+1}(J)=\max\limits_{J_{r+1}\in M_{r+1}}\mu(J_{r+1}).$

It remains to apply the Theorem 8 to obtain the explicit form of
$\mu(J_{r+1})$.

∎

4.2. An analogue of the Chebyshev alternance theorem

In the statement 2, it was shown that for the optimal solution in the residual
vector, the maximum absoulte values are achieved in at least $r+1$ positions.
The result on the Chebyshev alternance for continuous functions is widely
known. For continuous functions it states, in addition to the fact that the
maximum abosulte values are reached in the residual vector, that there is an
alternation of signs. A similar result can be proved in the matrix case.

######  Lemma 3.

Suppose we need to solve the problem of approximating the vector
$a\in\mathbb{R}^{n}$ by the system of vectors $V\in\mathbb{R}^{n\times r}$ and
that the vector $z^{*}$ is the vector of the best approximation (the best
equidistant point of the system). Denote by $w=a-Vz^{*}$ the residual vector.
Then the signs of the quantities

$w_{1}D_{1},w_{2}D_{2},\dots,w_{n+1}D_{n+1}$ (6)

alternate.

###### Proof.

In the notation of Theorems 7 and 8 we have that

$z^{*}=\sum\limits_{j=1}^{n+1}\dfrac{|D_{j}|}{\sum\limits_{\nu=1}^{n+1}|D_{\nu}|}z^{j}.$

Moreover, from the Theorem 7 we have that

$(v^{j},z^{j})-a_{j}=\dfrac{(-1)^{j+1}}{D_{j}}\sum\limits_{\nu=1}^{n+1}(-1)^{\nu}a_{\nu}D_{\nu}=\dfrac{(-1)^{j+1}}{D_{j}}X,$

where

$X=\sum\limits_{\nu=1}^{n+1}(-1)^{\nu}a_{\nu}D_{\nu}$

does not depend on $j$. According to the definition $z^{j}$,

$Vz_{j}=\begin{bmatrix}a_{1}&a_{2}&\dots&a_{j-1}&\widetilde{a}_{j}&a_{j+1}&\dots&a_{n+1}\end{bmatrix}^{T},$

where $\widetilde{a}_{j}=(v^{j},z^{j})$. Then

$Vz^{*}=\sum\limits_{j=1}^{n+1}\dfrac{|D_{j}|}{\sum\limits_{\nu=1}^{n+1}|D_{\nu}|}\begin{bmatrix}a_{1}\\\
a_{2}\\\ \vdots\\\ a_{j-1}\\\ \widetilde{a}_{j}\\\ a_{j+1}\\\ \vdots\\\
a_{n+1}\end{bmatrix}=\begin{bmatrix}a_{1}\\\ a_{2}\\\ \vdots\\\ a_{j-1}\\\
a_{j}\\\ a_{j+1}\\\ \vdots\\\
a_{n+1}\end{bmatrix}-\dfrac{1}{\sum\limits_{\nu=1}^{n+1}|D_{\nu}|}\left(\begin{bmatrix}|D_{1}|\widetilde{a}_{1}\\\
|D_{2}|\widetilde{a}_{2}\\\ \vdots\\\ |D_{j-1}|\widetilde{a}_{j-1}\\\
|D_{j}|\widetilde{a}_{j}\\\ |D_{j+1}|\widetilde{a}_{j+1}\\\ \vdots\\\
|D_{n+1}|\widetilde{a}_{n+1}\end{bmatrix}-\begin{bmatrix}|D_{1}|a_{1}\\\
|D_{2}|a_{2}\\\ \vdots\\\ |D_{j-1}|a_{j-1}\\\ |D_{j}|a_{j}\\\
|D_{j+1}|a_{j+1}\\\ \vdots\\\ |D_{n+1}|a_{n+1}\end{bmatrix}\right).$

From here

$a-Vz^{*}=\dfrac{1}{\sum\limits_{\nu=1}^{n+1}|D_{\nu}|}\cdot\begin{bmatrix}|D_{1}|(a_{1}-\widetilde{a}_{1})\\\
|D_{2}|(a_{2}-\widetilde{a}_{2})\\\ \vdots\\\
|D_{n+1}|(a_{n+1}-\widetilde{a}_{n+1})\\\
\end{bmatrix}=\dfrac{1}{\sum\limits_{\nu=1}^{n+1}|D_{\nu}|}\cdot\begin{bmatrix}|D_{1}|\dfrac{(-1)^{1}}{D_{1}}X\\\
|D_{2}|\dfrac{(-1)^{2}}{D_{2}}X\\\ \vdots\\\
|D_{n+1}|\dfrac{(-1)^{n+1}}{D_{n+1}}X\\\ \end{bmatrix},$

since

$a_{j}-\widetilde{a}_{j}=a_{j}-(v^{j},z^{j})=\dfrac{(-1)^{j}}{D_{j}}X.$

Denoting

$C=\dfrac{X}{\sum\limits_{\nu=1}^{n+1}|D_{\nu}|},$

we get that

$w=a-Vz^{*}=C\begin{bmatrix}(-1)^{1}\operatorname*{sign}D_{1}\\\
(-1)^{2}\operatorname*{sign}D_{2}\\\ \vdots\\\
(-1)^{n+1}\operatorname*{sign}D_{n+1}\\\ \end{bmatrix}.$

And then

$w_{j}D_{j}=C(-1)^{j}|D_{j}|,$

and the sequence

$w_{1}D_{1},w_{2}D_{2},\dots,w_{n+1}D_{n+1}$

has alternating signs. ∎

4.3. Generalized Remez algorithm for matrices

Note that Lemma 3 shows that the matrix problem of the best approximation is
more general than a similar problem for continuous functions. Indeed, for
continuous functions, as well as for matrices, the result is known that there
exists a characteristic set of $r+1$ elements when approximating by a system
of $r$ functions (i.e. by polynomials of degree $r-1$). With a known
characteristic set, the problem is reduced to solving a matrix problem with a
Vandermond matrix. Note that the determinant of the Vandermonde matrix can be
calculated by the formula

$W(x_{1},x_{2},\dots,x_{r})=\prod\limits_{j<i}(x_{i}-x_{j}).$

Hence it is easy to see that the sign of the determinant of the Vandermonde
matrix depends only on the order in which the points are taken. If the points
are taken in ascending order each time, then all determinants have the same
sign and in the formula (6) only the signs of the residual elements remain.
This reasoning allows us to generalize the Remez algorithm for constructing
the best Chebyshev approximation to the matrix case.

Note that the theorem 11 already allows us to solve the problem (4) in a
finite number of operations. To do this, it is enough to iterate over all
possible variants of characteristic sets (all possible sets of $r+1$ rows) and
solve for each of them the problem of finding the best equidistant point.
However, it is possible to find the characteristic set much faster.

Let us present an algorithm for solving the problem of the best Chebyshev
approximation in the real case. For given matrix $V\in\mathbb{R}^{n\times r}$
and vector $a\in\mathbb{R}^{n}$:

  1. 1.

Choose an arbitrary set of $r+1$ indices of the rows of the matrix $V$. Denote
this set by $I_{1}$ and take $t=1$.

  2. 2.

Solve the problem of the best uniform approximation for the matrix $V(I_{t})$
and the vector $a(I_{t})$. This problem can be solved in $O(r^{3})$ operations
for the Chebyshev system of vectors. Denote the solution by $u_{t}$.

  3. 3.

Calculate the residual $w_{t}=Vu_{t}-a$ and find the element of $w_{t}$ with
the maximum absolute value. This requires $O(nr)$ operations. Denote the
position of this element by $j_{t}$. If $j_{t}\in I_{t}$, then according to
the note to the Remez criterion, the set $I_{t}$ is characteristic and $u_{t}$
is the solution to the problem of the best approximation.

  4. 4.

If $j_{t}\notin I_{t}$, then we try to replace each of the elements of the set
$I_{t}$ by $j_{t}$. Let $I_{t}=\\{i_{1}^{t},i_{2}^{t},\dots,i_{r+1}^{t}\\}$.
We denote $I_{t}^{k}=I_{t}\setminus\\{i_{k}^{t}\\}\cup j_{t}$. Solve the
problem with the matrix $V(I_{t}^{k})$ and the vector $a(I_{t}^{k})$ and find
the maximum of the absolute values in the residual on the set $I_{t}^{k}$,
$w_{t}^{k}=V(I_{t}^{k})u_{t}^{k}-a(I_{t}^{k})$. Let
$l=\operatorname*{arg\,max}\limits_{k}\|w_{t}^{k}\|_{\infty}$. This step
requires $O(r^{4})$ operations

  5. 5.

$I_{t+1}=I_{t}^{l}$, $t=t+1$ and go to step 2.

######  Theorem 12.

Let a system of vectors $V\in\mathbb{R}^{n\times r}$ be Chebyshev and let
$a\in\mathbb{R}^{n}$. Then the generalized Remez algorithm finds the solution
to the problem of the best approximation in a finite number of operations.

###### Proof.

Let $I_{t}$ be the current set of indices and $w_{t}=Vu_{t}-a$. Denote

$E_{t}=\|w_{t}(I_{t})\|_{\infty}.$

Assume that in the vector $w_{t}$ the element with the maximum absolute value
is attained at the position $j_{t}$. Then consider the problem of the best
approximation for the submatrix taken on the set of rows with numbers
$I_{t}\cup\\{j_{t}\\}$. For this problem, there is a characteristic set of
$r+1$ elements. Note that it cannot entirely consist of elements of the set
$I_{t}$, since for an optimal solution on this set, a strictly larger value of
the residual element is attained in the position $j_{t}$. This means that the
characteristic set contains $j_{t}$ and $r$ elements from the set $I_{t}$,
that is, it is obtained by replacing one of the elements in $I_{t}$ with
$j_{t}$. Let us denote this set by $\widehat{I}_{t}$. Let us show that in this
case the error of the optimal approximation on the new set $\widehat{I}_{t}$
is strictly greater than on the set $I_{t}$. Indeed, assume that the error of
the optimal approximation on the set $I_{t}$ is $\delta$, and that the
corresponding solution gives the error $\varepsilon$ on the element in the
position $j_{t}$. Note that $\varepsilon>\delta$. Similarly, let the optimal
approximation on the set $\widehat{I}_{t}$ on the set itself get the error
$\delta_{1}$, and on the element removed from $I_{t}$, the error
$\varepsilon_{1}$. Note that since $\widehat{I}_{t}$ is a characteristic set,
then $\varepsilon\leq\delta_{1}$. Then

$\delta<\varepsilon\leq\delta_{1},$

whence it follows that the error of the optimal approximation on the new set
$\widehat{I}_{t}$ is strictly greater than the error of the optimal
approximation on the set $I_{t}$. Hence it follows that

$E_{t+1}>E_{t}.$

But since there are finitely many subsets of size $r+1$, the sequence
$\\{E_{t}\\}$ cannot be infinite and reaches its maximum value on some set,
which, according to the reasoning of Theorem 11, indicates that the found set
is characteristic and optimal solution is constructed.

∎

5\. ON THE PROBLEM OF THE CHEBYSHEV APPROXIMATION OF MATRICES

Having built a method for solving the problem (3), we can go to the problem

$\mu=\inf\limits_{U\in\mathbb{R}^{m\times r},V\in\mathbb{R}^{n\times
r}}\left\|A-UV^{T}\right\|_{C}.$ (7)

5.1. Necessary condition for optimality

In [9], the necessary condition for the optimality of the solution of the
problem (7) was proved. In light of the results obtained above, we can easily
obtain this condition and also generalize it to the case of arbitrary rank.
Let the pair $(\widehat{U},\widehat{V})$ be a solution to the problem (7).
Then the matrix $\widehat{U}$ is a solution to the problem

$\mu=\inf\limits_{U\in\mathbb{R}^{m\times
r}}\left\|A-U\widehat{V}^{T}\right\|_{C}.$

Assume that that the element of the matrix $A-\widehat{U}\widehat{V}^{T}$ with
maximum absolute value is at position $(i,j)$. Consider the problem for the
$i$-th row of the matrix

$\mu=\inf\limits_{u\in\mathbb{R}^{m\times
r}}\left\|a^{i}-u\widehat{V}^{T}\right\|_{C}.$ (8)

It is clear that $\widehat{u}^{i}$ is the optimal solution to the problem (8),
otherwise it would be possible to replace the $i$-th row of the matrix
$\widehat{U}$ with the optimal solution and obtain better result in problem
(7). By virtue of the optimality of the solution, we have that in the vector
$a^{i}-\widehat{u}^{i}\widehat{V}^{T}$ the maximum absolute value is attained
at $r+1$ position and the signs of the residual and determinants of the matrix
$\widehat{V}$ in these positions alternate (see Lemma 3). To obtain the
necessary condition from [9], it suffices to note that for $r=1$ the
determinants are the elements of the vector $\widehat{V}$, and the sign of
$\widehat{u}^{i}$ obviously does not change within one column from which
Statement 1 follows. In the case of arbitrary rank in each column and each row
in which there is an element with maximum absolute value, the maximum absolute
value is reached at $r+1$ positions and the signs of the residual and
determinants alternate according to Lemma 3.

5.2. Solving method

Let us build an iterative process for solving the problem (7). Let a matrix
$A\in\mathbb{R}^{m\times n}$ and a Chebyshev matrix $U_{0}$ be given. Let us
find the best approximation $A=U_{0}V^{T}$ and denote the result by $V_{1}$.
Suppose that the system of vectors $V_{1}$ is Chebyshev. Then we find the best
approximation $A=UV_{1}^{T}$ and denote the result by $U_{1}$, again assuming
that the system $U_{1}$ is Chebyshev. Let us find the best approximation
$A=U_{1}V^{T}$ and denote the result by $V_{2}$. Continuing according to the
described scheme, we note that the quantity
$\rho_{k}=\|A-U_{k}V_{k}^{T}\|_{C}$ does not increase and is bounded below
and, therefore, converges.

6\. NUMERICAL EXPERIMENTS

In this section, we present a number of numerical experiments, where we apply
the method described in Section 5.2 to construct low-rank Chebyshev
approximations for matrices whose singular values do not decrease. For the
experiments, the algorithm from Section 5.2 was implemented in C++. In the
experiment, random matrices were generated with singular values uniformly
distributed on $[1,2]$. For this, two random matrices are generated from the
standard normal distribution, a QR decomposition is constructed for them, and
the factors $Q$ are chosen as the left and right singular vectors. The
singular value matrix $\Sigma$ is generated as a diagonal matrix such that its
diagonal elements are uniformly distributed on $[1,2]$. After that, the matrix
$U\Sigma V^{T}$ is built. The sizes of the matrices vary from 10 to 1400 with
a step of 10, and the approximation rank is chosen as $r=\sqrt{n}$, where $n$
is the size of the matrix. For each size, 10 random matrices are generated,
and for each of them, the alternance method of 20 random points is launched.
Thus, for each size, there are 200 runs of the alternance method. For each
matrix, the mean value of the accuracy $\mu_{n}^{i}$ and the variance
$\sigma_{n}^{i}$ of the Chebyshev approximation over 20 starting points are
calculated. Further, for each size, these values are averaged over 10 matrices

$\mu_{n}=\dfrac{1}{10}\sum\limits_{i=1}^{10}\mu_{n}^{i},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\sigma_{n}=\dfrac{1}{10}\sum\limits_{i=1}^{10}\sigma_{n}^{i}.$

(a) Approximation error

(b) Variance

Fig. 1. Averaged approximation error and variance over 20 random initial
conditions and 10 random matrices for different matrix sizes.

Fig. 2. Averaged approximation error over 20 random initial conditions and 10
random matrices of different sizes, and its fitted approximation.

Fig. 3. Averaged execution time over 200 runs for matrices of different sizes,
and its fitted approximation.

In Fig. 1a, we plot $\mu_{n}$ against the size of the matrix, and in Fig. 1b
we present the corresponding plot for $\sigma_{n}$; the latter is shown in
logarithmic scale. An interesting observation is that variance decays as the
size of the problem grows. For instance, for a matrix of sizes $1400\times
1400$, if we approximate it with rank $37$ with 20 different random initial
conditions, we get the following approximation errors:

$\begin{bmatrix}0.09111796&0.09098914&0.09103979&0.09101653&0.09097955\\\
0.09112523&0.09102086&0.09097652&0.09099676&0.0909908\\\
0.09106326&0.0911168&0.09108753&0.09101277&0.09098213\\\
0.09103401&0.09106984&0.09097417&0.09094869&0.09092307\end{bmatrix}.$

We also estimated the asymptotic dependence of the approximation error on the
matrix sizes. To this end, we fitted a parametric curve
$\dfrac{c\log^{\alpha}n}{n^{\beta}}$. The optimal parameter values that we
found are

$\begin{cases}c=0.995139,\\\ \alpha=0.604346,\\\ \beta=0.495001.\\\
\end{cases}$

The curve $\dfrac{c\log^{\alpha}n}{n^{\beta}}$ with the optimal parameters is
presented in Fig. 2. It is worth noting that this estimate corresponds to

$\varepsilon\approx\dfrac{\log^{0.6}{n}}{n^{0.5}},$

while the known proved bound (see Thm. 1 [7]) for $r=\sqrt{n}$ gives

$\varepsilon\leq\dfrac{6\sqrt{2}\log^{0.5}{(2n+1)}}{n^{0.25}},$

which shows that the latter is not optimal.

In addition, we measured the execution time of our algorithm. For every
problem size, we averaged the time over 200 runs. In Fig. 3, we plot the
execution time against the matrix size. We also approximated the experimental
curve by fitting $cn^{\alpha}$. The optimal parameters are

$\begin{cases}c=9.13302\mathrm{e}{-09}\\\ \alpha=3.49745\\\ \end{cases}$

This means that for $r=\sqrt{n}$ the computational complexity is $O(n^{3.5})$
in practice.

7\. CONCLUSION

In this work, a method is proposed for solving the problem of the best low-
rank approximation of matrices in the Chebyshev norm in the case when one of
the factors of skeleton decomposition is known. Using the proposed scheme and
the alternance method, an algorithm was constructed for computing low-rank
approximations in the Chebyshev norm for an arbitrary rank. The described
method essentially generalizes all known methods for solving the problem of
Chebyshev approximations of matrices and improves the known theoretical
estimates of the approximation described in [7]. Numerical experiments show
that the method is capable of approximating matrices with good accuracy even
in the absence of decay of singular values and has an acceptable asymptotic
complexity.

## References

  * 1. _Bebendorf M._ A means to efficiently solve elliptic boundary value problems // Hierarchical Matrices. LNCS. 2008. V. 63. P. 49-98
  * 2. _Goreinov S., Tyrtyshnikov E., Zamarashkin N._ A theory of pseudoskeleton approximations // Linear Algebra and its Applications. 1997. V. 261. N. 1. P. 1-21
  * 3. _He X., Zhang H., Kan M. Y., Chua T. S._ Fast matrix factorization for online recommendation with implicit feedback. // Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval. 2016. P. 549-558
  * 4. _Halko N., Martinsson P., Tropp J._ Finding Structures with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions // SIAM Review. 2011. V. 53. N. 2. P. 217-288
  * 5. _Osinsky A., Zamarashkin N._ Pseudo-skeleton approximations with better accuracy estimates // Linear Algebra and its Applications. 2018. V. 537. P. 221-249
  * 6. _Son S. W., Chen Z., Hendrix W., Agrawal A., Liao W. K., Choudhary A._ Data compression for the exascale computing era-survey // Supercomputing frontiers and innovations. 2014. V. 1. N. 2. P. 76-88
  * 7. _Udell M., Townsend A._ Why are big data matrices approximately low rank? // SIAM Journal on Mathematics of Data Science. 2019. V. 1. N. 1. P. 144-160
  * 8. _Yang C., Akimoto Y., Kim D., Udell M._ Oboe: Collaborative filtering for automl initialization // arXiv preprint arXiv:1808.03233. 2018
  * 9. _Daugavet V._ On the uniform approximation of a function of two variables, given by a table, by the product of functions of one variable // Journal of Computational Mathematics and Mathematical Physics. 1971. V. 11. N. 2. P. 289-303
  * 10. _Dzyadyk V. K._ Introduction to the theory of uniform approximation of functions by polynomials // Nauka. 1977
  * 11. _Dzyadyk V. K._ On the approximation of functions on sets consisting of a finite number of points // Collection of "Theory of approximation of functions and its applications" . 1974. P. 69-80
  * 12. _Smirnov V. I., Lebedev N. A._ Constructive theory of functions of a complex variable // M. 1964


# Curve neighborhoods of Seidel products in quantum cohomology

Mihail Țarigradschi  Department of Mathematics, Rutgers University, 110
Frelinghuysen Road, Piscataway, NJ 08854, USA<EMAIL_ADDRESS>
###### Abstract.

A conjecture of Buch–Chaput–Perrin asserts that the two-pointed curve
neighborhood corresponding to a quantum product of Seidel type is an
explicitly given Schubert variety. We prove this conjecture for flag varieties
in type $A$.

The author was partially supported by NSF grant DMS-2152316.

##  1\. Introduction

Given a flag variety $X=G/P_{X}$, the Seidel representation on the small
quantum cohomology ring $\operatorname{QH}(X)|_{q=1}$ specialized at $q=1$ can
be described combinatorially, see [belkale_transformation_2004,
chaput_affine_2009]. In the recent paper [buch_seidel_2023], this action is
extended to the quantum K-theory ring $\operatorname{QK}(X)|_{q=1}$ when $X$
is cominuscule, and it is found that similar identities hold. On
$\operatorname{QH}(X)$ it is realized as the action of a subgroup
$W^{\operatorname{{comin}}}\subset W$ through the identity

(1) $[X^{w}]\star[X^{u}]=q^{d}[X^{wu}],$

where $w\in W^{\operatorname{{comin}}}$, $u\in W$, and $d=d_{\min}(w,u)\in
H_{2}(X,{\mathbb{Z}})$ denotes the smallest degree of a rational curve
connecting general translates of $X^{w}$ and $X^{u}$. The subgroup
$W^{\operatorname{{comin}}}$ consists of the identity and the minimal length
representatives of the longest Weyl group element $w_{0}$ in $W^{M}=W/W_{M}$
for each cominuscule flag variety $M=G/P_{M}$:

$W^{\operatorname{{comin}}}=\\{1\\}\cup\\{(w_{0})^{M}:M=G/P_{M}\text{ where
$M$ is a cominuscule variety}\\},$

here $(w_{0})^{M}\in W$ denotes the representative of $w_{0}$ in $W^{M}$.

Equation (1) also implies the following identity:

$[X^{w}]\star[X^{u}]=q^{d}[\Gamma_{d}(X_{w_{0}w},X^{u})],$

where $\Gamma_{d}(X_{w_{0}w},X^{u})$ is the two-pointed curve neighborhood
defined as the union of all stable curves of degree $d$ that pass through
$X_{w_{0}w}$ and $X^{u}$.

This led the authors of [buch_seidel_2023] to conjecture that
$\Gamma_{d}(X_{w_{0}w},X^{u})$ is a translate of $X^{wu}$:

######  Conjecture 1 ([buch_seidel_2023], Conjecture 3.11).

Let $X=G/P_{X}$ be any flag variety. For $u\in W,w\in
W^{\operatorname{{comin}}}$, and $d=d_{\min}(w,u)\in H_{2}(X,{\mathbb{Z}})$,
we have

$\Gamma_{d}(X_{w_{0}w},X^{u})=w^{-1}.X^{wu}.$

It is known that the conjecture holds in the following cases:

  * •

$d=0$ (see [buch_seidel_2023]*Proposition 2.2);

  * •

$X$ is cominuscule and $w=w_{0}^{X}$ (see [buch_seidel_2023]*Lemma 3.1);

  * •

$X=\operatorname{Gr}(k,n)$ and $w=w_{0}^{{\mathbb{P}}^{n-1}}$ (see
[li_seidel_2022]*Proposition 4.5).

In this paper we consider the following specialization:

######  Conjecture 2.

Let $X=G/P_{X}$ be a flag variety where $P_{X}$ is a maximal parabolic
subgroup of $G$. For $u\in W,w\in W^{\operatorname{{comin}}}$, and
$d=d_{\min}(w,u)\in H_{2}(X,{\mathbb{Z}})$, we have

$\Gamma_{d}(X_{w_{0}w},X^{u})=w^{-1}.X^{wu}.$

We prove the following reduction theorem.

######  Theorem 3.

Conjecture 1 follows from Conjecture 2 for the same $G$.

And then prove Conjecture 2 for Grassmannians of type A to conclude that
Conjecture 1 holds for flag varieties of type A. Our proof is inspired from a
description of two-pointed curve neighborhoods in Grassmannians given in
[li_seidel_2022]*Proposition 4.5.

### Acknowledgements

We thank Anders Buch for useful discussions and bringing to our attention
Conjecture 1.

##  2\. Notation and Preliminaries

Let $G$ be a complex semisimple linear algebraic group, let $T\subset B$ be a
maximal torus and a Borel subgroup of $G$. Denote by $B^{-}$ the Borel
subgroup opposite to $B$, by $\Phi$ the set of roots of $G$, by
$\Delta\subset\Phi$ the set of simple roots, and by $W$ the Weyl group of $G$.

Let $P_{X}\supseteq B$ be a parabolic subgroup of $G$. In the flag variety
$X=G/P_{X}$ we consider the Schubert varieties
$X_{u}=\overline{BuP_{X}/P_{X}}$ and $X^{u}=\overline{B^{-}uP_{X}/P_{X}}$
where $u\in W$. Let $W_{X}$ be the Weyl group of $P_{X}$, then we denote
$W^{X}\subset W$ to be the set of minimal length representatives of the cosets
in $W/W_{X}$. For an element $u\in W$, denote by $u^{X}\in W^{X}$ the
representative of $uW_{X}\in W/W_{X}$. Let $\Delta_{P_{X}}\subseteq\Delta$ be
the set of simple roots that define $P_{X}$, i.e. $\beta\in\Delta_{P_{X}}\iff
s_{\beta}\in W_{X}$.

Recall the general construction of curve neighborhoods (described for example
in [buch_finiteness_2013]). Let $\overline{{\mathcal{M}}}_{0,3}(X,d)$ denote
the moduli space of $3$-pointed, genus $0$ stable maps to $X$ of effective
degree $d\in H_{2}(X,{\mathbb{Z}})$. We have the evaluation maps
$ev_{i}:\overline{{\mathcal{M}}}_{0,3}(X,d)\to X$ where $i\in\\{1,2,3\\}$ that
correspond to taking the image of the $i$-th marked point. Given two opposite
Schubert varieties $X_{u},X^{v}$, define the Gromov–Witten variety
$M_{d}(X_{u},X^{v})=ev_{1}^{-1}(X_{u})\cap
ev_{2}^{-1}(X^{v})\subset\overline{{\mathcal{M}}}_{0,3}(X,d)$. It describes
the coefficients in the quantum product of Schubert classes in
$\operatorname{QH}(X)$:

(2) $[X_{u}]\star[X^{v}]=\sum_{d\geq 0}(ev_{3})_{*}[M_{d}(X_{u},X^{v})]q^{d}.$

We denote $\Gamma_{d}(X_{u},X^{v})=ev_{3}(M_{d}(X_{u},X^{v}))$. The subvariety
$\Gamma_{d}(X_{u},X^{v})\subset X$ is called a two-pointed curve neighborhood
and consists of the union of all stable curves of degree $d$ that pass through
$X_{u}$ and $X^{v}$.

##  3\. Proof of the reduction to maximal parabolics

In this section, we prove Theorem 3. The main observation is the fact that the
intersection of Schubert varieties $X^{u^{Y}}$ for appropriate “smaller” flag
varieties $Y$ is the Schubert variety $X^{u}$, this follows from a
combinatorial fact from [bjorner_combinatorics_2005].

######  Lemma 4.

Let $X=G/P_{X}$ be a flag variety, $F\subseteq X$ a subvariety, $w\in W$, and
$g\in G$. Let $Y=G/P_{Y},Z=G/P_{Z}$ be flag varieties such that $P_{Y}\cap
P_{Z}=P_{X}$. Denote by $p:X\to Y$ and $q:X\to Z$ the projection maps, assume
that $p(F)\subseteq g.Y^{w}$ and $q(F)\subseteq g.Z^{w}$. Then $F\subseteq
g.X^{w}$.

###### Proof.

Using [buch_seidel_2023]*Lemma 2.1(e) we have

$F\subseteq p^{-1}(p(F))\subseteq p^{-1}(g.Y^{w})=g.X^{w^{Y}}.$

By the same argument for $Z$, we have $F\subseteq g.X^{w^{Z}}$, so that
$F\subseteq g.(X^{w^{Y}}\cap X^{w^{Z}})$. By
[bjorner_combinatorics_2005]*Theorem 2.6.1, using
$\Delta_{P_{Y}}\cap\Delta_{P_{Z}}=\Delta_{P_{X}}$, the elements $w^{Y},w^{Z}$
have a well-defined join equal to $w^{X}$ in the poset $W^{X}$. In particular
$X^{w^{Y}}\cap X^{w^{Z}}=X^{w^{X}}=X^{w}$, and we are done. ∎

###### Proof of Theorem 3.

By [buch_finiteness_2013]*Corollary 3.3, the two-pointed Gromov–Witten variety
$M_{d}(X_{w_{0}w},X^{u})\subset\overline{\mathcal{M}}_{0,3}(X,d)$ is
irreducible, and so is
$\Gamma_{d}(X_{w_{0}w},X^{u})=\operatorname{ev}_{3}(M_{d}(X_{w_{0}w},X^{u}))\subset
X$. In the graded ring $\operatorname{QH}(X)$, by
[belkale_transformation_2004, chaput_affine_2009] we have the identity
$[X_{w_{0}w}]\star[X^{u}]=q^{d}[X^{wu}]$. On the other hand, from Equation (2)
we have

$[X_{w_{0}w}]\star[X^{u}]=q^{d}(ev_{3})_{*}[M_{d}(X_{w_{0}w},X^{u})]=q^{d}\deg(ev_{3})[\Gamma_{d}(X_{w_{0}w},X^{u})],$

so that $\deg(ev_{3})=1$, $[X^{wu}]=[\Gamma_{d}(X_{w_{0}w},X^{u})]$, and
$\operatorname{codim}X^{wu}=\operatorname{codim}\Gamma_{d}(X_{w_{0}w},X^{u})$.
Since Schubert varieties are irreducible, we are left with proving the
inclusion $\Gamma_{d}(X_{w_{0}w},X^{u})\subseteq w^{-1}.X^{wu}$.

We prove it by induction on $|\Delta\setminus\Delta_{X}|$. If
$|\Delta\setminus\Delta_{X}|=1$, we are done by assumption of Conjecture 2.

Otherwise, consider parabolic subgroups $P_{Y},P_{Z}\supsetneq P_{X}$ such
that $P_{Y}\cap P_{Z}=P_{X}$. Let $p:X\to Y=G/P_{Y}$, $q:X\to Z=G/P_{Z}$ be
the projections. Then
$p(\Gamma_{d}(X_{w_{0}w},X^{u}))\subseteq\Gamma_{p_{*}(d)}(Y_{w_{0}w},Y^{u})$.
Furthermore, $p_{*}(d_{\min}(w,u))=d_{\min}(w,u)\in H_{2}(Y,{\mathbb{Z}})$
(see [buch_euler_2020]*Section 2.3 or [chaput_affine_2009,
belkale_transformation_2004]). Applying induction to $Y$,
$\Gamma_{p_{*}(d)}(Y_{w_{0}w},Y^{u})\subseteq w^{-1}.Y^{wu}$, so that

$p(\Gamma_{d}(X_{w_{0}w},X^{u}))\subseteq\Gamma_{p_{*}(d)}(Y_{w_{0}w},Y^{u})\subseteq
w^{-1}.Y^{wu}.$

Analogously, we have $q(\Gamma_{d}(X_{w_{0}w},X^{u}))\subseteq w^{-1}.Z^{wu}$.
Using Lemma 4 for $F=\Gamma_{d}(X_{w_{0}w},X^{u})$, we are done. ∎

##  4\. Proof of the conjecture in type A

In this section we assume that the group $G$ is of type A. Identify $\Delta$
with the integers $\\{1,\dots,n-1\\}$ and $W$ with the symmetric group
$S_{n}$. When $P_{X}$ is the maximal parabolic corresponding to the simple
root $k$, i.e. $\Delta_{P_{X}}=\Delta\setminus\\{k\\}$, then $X$ is isomorphic
to the Grassmannian variety $\operatorname{Gr}(k,n)$ of $k$-planes in
${\mathbb{C}}^{n}$.

We have the isomorphism
$W^{\operatorname{{comin}}}\cong{\mathbb{Z}}/n{\mathbb{Z}}$, with a generator
$w\in S_{n}$ given by

$w(t)=\begin{cases}n,&\text{ if }t=1\\\ t-1,&\text{ if }2\leq t\leq
n\end{cases}.$

The element corresponding to the simple root $i\in\\{1,\dots,n-1\\}$ is given
by $w^{i}\in S_{n}$.

When $X=\operatorname{Gr}(k,n)$ is a Grassmannian, we can describe the two-
pointed curve neighborhoods using the quantum equals classical theorems (see
[buch_gromov-witten_2003]). For an effective degree $0\leq d\leq\min(k,n-k)$
we denote $Z_{d}=\operatorname{Fl}(k-d,d,k+d;n)$ to be the variety of three-
step flags of dimensions $(k-d,d,k+d)$ in ${\mathbb{C}}^{n}$. Similarly, we
denote $Y_{d}=\operatorname{Fl}(k-d,k+d;n)$ to be the variety of two-step
flags of dimensions $(k-d,k+d)$ in ${\mathbb{C}}^{n}$. We then have the
projection maps $p_{d}:Z_{d}\to X$, $q_{d}:Z_{d}\to Y_{d}$ and
$\Gamma_{d}(X_{u},X^{v})=p_{d}(Z_{d}(X_{u},X^{v}))$ where
$Z_{d}(X_{u},X^{v})=q_{d}^{-1}(q_{d}(p_{d}^{-1}(X_{u}))\cap
q_{d}(p_{d}^{-1}(X^{v})))\subset Z_{d}$. Analogous to Equation (2),

$[X_{u}]\star[X^{v}]=\sum_{d\geq 0}(q_{d})_{*}[Z_{d}(X_{u},X^{v})]q^{d}.$

Recall that Grassmannian Schubert varieties can be equivalently indexed by a
partition. Fix a basis $e_{1},\dots,e_{n}$ of ${\mathbb{C}}^{n}$ such that $B$
acts on ${\mathbb{C}}^{n}$ by upper-triangular matrices. Consider the complete
flag $E_{\bullet}=E_{1}\subset E_{2}\subset\dots\subset E_{n}$ where
$E_{i}=\operatorname{Span}\\{e_{1},\dots,e_{i}\\}$, then
$B.E_{\bullet}=E_{\bullet}$. Similarly, consider the opposite flag
$E^{\operatorname{{opp}}}_{\bullet}=E^{\operatorname{{opp}}}_{1}\subset
E^{\operatorname{{opp}}}_{2}\subset\dots\subset E^{\operatorname{{opp}}}_{n}$
where
$E^{\operatorname{{opp}}}_{i}=\operatorname{Span}\\{e_{n},\dots,e_{n-i+1}\\}$,
then
$B^{-}.E_{\bullet}^{\operatorname{{opp}}}=E_{\bullet}^{\operatorname{{opp}}}$.

Given a partition $\lambda=(\lambda_{1},\dots,\lambda_{k})$ such that
$n-k\geq\lambda_{1}\geq\dots\geq\lambda_{k}\geq 0$, define the $B$-stable
Schubert variety

$X_{\lambda}=\\{\Sigma\in X:\dim\Sigma\cap E_{i+\lambda_{k-i+1}}\geq i\
\text{for }i=1,\dots,k\\},$

of dimension $\dim X_{\lambda}=|\lambda|$, and the $B^{-}$-stable Schubert
variety

$X^{\lambda}=\\{\Sigma\in X:\dim\Sigma\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\geq i\ \text{for }i=1,\dots,k\\}$

of codimension $\operatorname{codim}X^{\lambda}=|\lambda|$.

These varieties satisfy $X_{\lambda}=X_{w}$ and $X^{\lambda}=X^{w}$ where
$w\in W^{X}\subset S_{n}$ is the permutation of minimal length such that
$\lambda=(w(k)-k,w(k-1)-(k-1),\dots,w(1)-1)$. We will also think of $\lambda$
as a Young diagram inside a $k\times(n-k)$ rectangle such that row $i$ has
$\lambda_{i}$ boxes.

######  Theorem 5.

Let $X=\operatorname{Gr}(k,n)$. For $u\in W$, $w\in
W^{\operatorname{{comin}}}$, and $d=d_{\min}(w,u)\in H_{2}(X,{\mathbb{Z}})$,
we have

$\Gamma_{d}(X_{w_{0}w},X^{u})=w^{-1}.X^{wu}$

###### Proof.

If $w=1$, then $d=0$ and
$\Gamma_{d}(X_{w_{0}w},X^{u})=\Gamma_{0}(X_{w_{0}},X^{u})=X_{w_{0}}\cap
X^{u}=X^{u}=w^{-1}.X^{wu}$. Assume $w\neq 1$.

Let $\beta\in\Delta$ be a simple root that indexes $w$. Using the duality
isomorphism $\operatorname{Gr}(k,n)\cong\operatorname{Gr}(n-k,n)$, we may
assume $\beta\geq k$. As an element of $S_{n}$, $w_{0}w=(\beta\ (\beta-1)\
\dots\ 1\ n\ (n-1)\ \dots(\beta+1))$ in one-line notation. The corresponding
partition in $X$ is given by $(\beta-k,\beta-k,\dots,\beta-k)=(\beta-k)^{k}$.
Denote by $\lambda$ the partition associated to $u^{X}$.

We use [fulton_quantum_2004] to get an explicit expression for $d$. The degree
$d$ is the minimal degree of $q$ in
$[X_{(\beta-k)^{k}}]\star[X^{\lambda}]=[X^{(n-\beta)^{k}}]\star[X^{\lambda}]$.
Consider the overlap of $\lambda$ and the $180^{\circ}$ rotation of
$(n-\beta)^{k}$ in the $k\times(n-k)$ rectangle. This overlap is a partition,
call it $\lambda^{\prime}$, where we remove the left-most $(\beta-k)$ columns
from $\lambda$ (see Figure 1). Then $d$ is the length of the longest NW-SE
diagonal sequence of boxes in this overlap. Since $\lambda^{\prime}$ is a
partition, we can always move a NW-SE diagonal sequence of boxes to the NW
corner of $\lambda^{\prime}$. This gives the following formula for $d$:

(3) $d=\max(\\{0\\}\cup\\{j:\lambda_{j}-(\beta-k)\geq j\\}).$

Here is an example where $n=9,k=4,\lambda=(5,4,3,1),\beta=5$:

centertableaux  *(blue!40) & *(blue!40) *(blue!40) *(blue!40) *(blue!40)
*(blue!40) *(blue!40) *(blue!40) *(blue!40) *(blue!40) *(blue!40) *(blue!40)
*(blue!40)

a $\lambda$ given by the shaded region. Contour denotes the overlap.

centertableaux  *(blue!40) & *(blue!40) *(blue!40) *(blue!40) *(blue!40)
*(blue!40) *(blue!40) *(blue!40) *(blue!40)

b $\lambda^{\prime}$ given by the shaded region. Contour denotes a longest NW-
SE diagonal.

Figure 1. Finding $d$ from $\lambda$ and $\lambda^{\prime}$.

By the quantum equals classical theorem, we have that
$\Gamma_{d}(X_{w_{0}w},X^{u})=p_{d}(Z_{d}(X_{w_{0}w},X^{u}))$. Looking at the
three-step flags in $q_{d}^{-1}q_{d}p_{d}^{-1}(X^{u})\subset Z_{d}$, we have

$\displaystyle q_{d}^{-1}q_{d}p_{d}^{-1}(X^{u})$
$\displaystyle=q_{d}^{-1}q_{d}p_{d}^{-1}(X^{\lambda})$
$\displaystyle=\\{V_{k-d}\leq V_{k}\leq V_{k+d}:$
$\displaystyle\exists\widetilde{V_{k}}\text{ such that
}V_{k-d}\leq\widetilde{V_{k}}\leq V_{k+d}\text{ and }$
$\displaystyle\dim\widetilde{V_{k}}\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\geq i\text{ for }1\leq i\leq
k\\}$ $\displaystyle\subseteq\\{V_{k-d}\leq V_{k}\leq V_{k+d}:$
$\displaystyle\dim V_{k+d}\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\geq i\text{ for }1\leq i\leq
k\text{ and }$ $\displaystyle\dim V_{k-d}\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\geq i-d\text{ for }d+1\leq i\leq
k\\},$

where the last condition follows from $\dim V_{k-d}\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\geq\dim\widetilde{V_{k}}\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}-d\geq i-d$. By symmetry, for the
special case of $X_{w_{0}w}$, we have

$\displaystyle q_{d}^{-1}q_{d}p_{d}^{-1}(X_{w_{0}w})$
$\displaystyle=q_{d}^{-1}q_{d}p_{d}^{-1}(X_{(\beta-k)^{k}})$
$\displaystyle\subseteq\\{V_{k-d}\leq V_{k}\leq V_{k+d}:$ $\displaystyle\dim
V_{k+d}\cap E_{i+\beta-k}\geq i\text{ for }1\leq i\leq k\text{ and }$
$\displaystyle\dim V_{k-d}\cap E_{i+\beta-k}\geq i-d\text{ for }d+1\leq i\leq
k\\}$ $\displaystyle=\\{V_{k-d}\leq V_{k}\leq V_{k+d}:$ $\displaystyle
V_{k-d}\subset E_{\beta},\ \dim V_{k+d}\cap E_{\beta}\geq k\\}.$

Let
$V_{k}\in\Gamma_{d}(X_{w_{0}w},X^{u})=p_{d}(Z_{d}(X_{w_{0}w},X^{u}))=p_{d}(q_{d}^{-1}q_{d}p_{d}^{-1}(X_{w_{0}w})\cap
q_{d}^{-1}q_{d}p_{d}^{-1}(X^{u}))$. If $1\leq i\leq d$, then
$k-i+\lambda_{i}+1>\beta$ by (3), so that
$E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\cap E_{\beta}=0$ and

$\displaystyle\dim
V_{k}\cap(E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}+E_{\beta})$
$\displaystyle\geq\dim
V_{k+d}\cap(E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}+E_{\beta})-d$
$\displaystyle\geq\dim V_{k+d}\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}+\dim V_{k+d}\cap E_{\beta}-d\geq
i+k-d.$

Otherwise, if $d+1\leq i\leq k$, then $k-i+\lambda_{i}+1\leq\beta$ by (3), so
that $E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}+E_{\beta}={\mathbb{C}}^{n}$
and

$\displaystyle\dim V_{k}\cap(E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\cap
E_{\beta})$ $\displaystyle\geq\dim
V_{k-d}\cap(E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\cap E_{\beta})$
$\displaystyle=\dim V_{k-d}\cap
E^{\operatorname{{opp}}}_{n-k+i-\lambda_{i}}\geq i-d.$

For simplicity, we denote

(4) $G_{i}=\begin{cases}E^{\operatorname{{opp}}}_{n-k+(i+d)-\lambda_{i+d}}\cap
E_{\beta},&\text{if }1\leq i\leq k-d,\\\
E^{\operatorname{{opp}}}_{n-k+(i-k+d)-\lambda_{i-k+d}}+E_{\beta},&\text{if
}k-d+1\leq i\leq k.\end{cases}$

So that we have a chain of inclusions

$G_{1}\lneq G_{2}\lneq\dots\lneq G_{k-d}\lneq G_{k-d+1}\lneq\dots\lneq G_{k},$

and dimension conditions $\dim V_{k}\cap G_{i}\geq i$ for all $1\leq i\leq k$.

Note that the subspaces $G_{i}$ are parts of the complete flag
$F^{\operatorname{{opp}}}_{\bullet}$ defined by

$F^{\operatorname{{opp}}}_{i}=\begin{cases}\operatorname{Span}\\{e_{\beta},e_{\beta-1},\dots,e_{\beta-i+1}\\},&\text{if
}1\leq i\leq\beta\\\
\operatorname{Span}\\{e_{\beta},e_{\beta-1},\dots,e_{1},e_{n},\dots,e_{n-(i-\beta)+1}\\},&\text{if
}\beta+1\leq i\leq n\end{cases}$

which is precisely given by
$F_{\bullet}^{\operatorname{{opp}}}=w^{-1}.E_{\bullet}^{\operatorname{{opp}}}$.

The dimension conditions $\dim V_{k}\cap G_{i}\geq i$ for $1\leq i\leq k$
define a Schubert variety with respect to the flag
$F_{\bullet}^{\operatorname{{opp}}}$, it is given by

$\displaystyle\\{V_{k}:\dim V_{k}\cap G_{i}\geq i\text{ for }1\leq i\leq k\\}$
$\displaystyle=w^{-1}.\\{w.V_{k}:\dim V_{k}\cap G_{i}\geq i\text{ for }1\leq
i\leq k\\}$ $\displaystyle=w^{-1}.\\{V_{k}:\dim V_{k}\cap w.G_{i}\geq i\text{
for }1\leq i\leq k\\}$ $\displaystyle=w^{-1}.X^{v}$

for some $v\in W^{X}$.

We compute using (4)

$\displaystyle\ell(v)$
$\displaystyle=\operatorname{codim}w^{-1}.X^{v}=\sum(n-k+i-\dim G_{i})$
$\displaystyle=\sum_{1\leq i\leq k-d}(n-k+i-(\beta-k+i+d-\lambda_{i+d}))$
$\displaystyle+\sum_{k-d<i\leq k}(n-k+i-(\beta+n-k+(i-k+d)-\lambda_{i-k+d}))$
$\displaystyle=\sum_{1\leq i\leq k-d}(n-\beta-d+\lambda_{i+d})+\sum_{k-d<i\leq
k}(k-\beta-d+\lambda_{i-k+d})$ $\displaystyle=n(k-d)-\beta
k+|\lambda|=n(k-d)-\beta k+\ell(u^{X})$

On the other hand, from (1) and $[X^{w}]=[X_{w_{0}w}]$ we compute

$\displaystyle\ell((wu)^{X})$
$\displaystyle=\operatorname{codim}X^{wu}=\operatorname{codim}X_{w_{0}w}+\operatorname{codim}X^{u}-d\deg(q)$
$\displaystyle=\dim X-\dim X_{w_{0}w}+\ell(u^{X})-dn$
$\displaystyle=k(n-k)-(\beta-k)k+\ell(u^{X})-dn$ $\displaystyle=n(k-d)-\beta
k+\ell(u^{X})=\ell(v)$

Since $\Gamma_{d}(X_{w_{0}w},X^{u})\subseteq w^{-1}.X^{v}$ and $\dim
X^{v}=\dim X^{wu}=\dim\Gamma_{d}(X_{w_{0}w},X^{u})$ we get that the inclusion
is an equality. Since $[\Gamma_{d}(X_{w_{0}w},X^{u})]=[X^{wu}]$, we get
$v=(wu)^{X}$ from which the conclusion follows. ∎

By the above and Theorem 3, we conclude that Conjecture 1 holds in type A.

## References