CONDITION NUMBER BOUNDS FOR PROBLEMS WITH INTEGER COEFFICIENTS

GREGORIO MALAJOVICH

Abstract. An apriori bound for the condition number associated to each of the following problems is given: general linear equation solving, minimum squares, nonsymmetric eigenvalue problems, solving univariate polynomials, solving systems of multivariate polynomials. It is assumed that the input has integer coefficients and is not on the degenerate locus of the respective problem (i.e. the condition number is finite). Then condition numbers are bounded in terms of the dimension and of the bit-size of the input.

In the same setting, bounds are given for the speed of convergence of the following iterative algorithms: QR without shift for the symmetric eigenvalue problem, and Graeffe iteration for univariate polynomials.

1. Introduction

In most of the numerical analysis literature, complexity and stability of numerical algorithms are usually estimated in terms of the problem instance dimension and of a ‘condition number’.

For instance, the complexity of solving an n × n linear system Ax = b is usually estimated in terms of the dimension n (actually the input size is n(n + 1)) and of the condition number κ(A) = ∥ A ∥_{2} ∥ A^{−1} ∥_{2} .

There is a set of problems instances with κ(A) = ∞, and in most cases it makes no sense to attempt solving those problem instances. There are also problem instances (in our case, matrices) close to the locus of degenerate problem instances. Those will have a large condition number, and will be said to be ill-conditioned.

It is usually accepted that ill-conditioned problem instances are hard to solve. Thus, for complexity purposes a problem instance with a large condition number should be considered ‘large’. Therefore, when considering problems defined for real inputs, a reasonable measure for the input size would be (in our example): n^{2} log_{2} κ(A). (Compare to [13] Formula 2.1 and paragraph below. See also the discussion in [1], Chapter 3, Section 1).

2 GREGORIO MALAJOVICH^{1}

Another tradition, derived from classical complexity theory and pervasive in several branches of literature (such as linear programming), is to consider the subset of problems instances with integer coefficients. Hence the input size is the number of coefficients times the bit-size of the largest coefficient (in absolute value).

Date: February 12, 1999.

DEPARTAMENTO DE MATEMÁTICA APLICADA, UNIVERSIDADE FEDERAL DO RIO DE JANEIRO. CAIXA POSTAL 68530, CEP 21945, RIO DE JANEIRO, RJ, BRASIL.

E-MAIL: GREGORIO@LABMA.UFRJ.BR. ON LEAVE AT MSRI, 1000 CENTENNIAL DRIVE, BERKELEY CA 94720-5070. E-MAIL: GREGORIO@MSRI.ORG

In this paper, the following classical problems of numerical analysis are considered:

1. Solving a general n × n system of linear equations.

2. Minimal squares problem for a full-rank matrix.

3. Non-symmetric eigenvalue problem.

4. Solution of one univariate polynomial.

5. Solution of a non-degenerate system of n polynomial equations in n variables. All those problems share the feature mentioned above: there is a degenerate locus,

and problem instances with real coefficients can be as close to the degenerate locus as wished. This implies that they can be arbitrarily ill-conditioned.

However, in Theorems 1 to 5 below, we provide bounds for the condition number of problems instances with integer coefficients and not in the degenerate locus. Those bounds depend on the dimension (size) of the problem instance and on the bit-size of its coefficients.

In the analysis of iterative algorithms, one further considers a certain quantity that can be used to bound the speed of convergence and hence the number of iterations to obtain a given approximation. For instance, for power methods (or QR iteration without shift) in the symmetric eigenvalue problem, one can bound the number of steps in terms of the desired accuracy and of the ratio between different eigenvalues. The farther this number is from 1, the faster is the convergence.

Once again, if input has real coefficients, this quantity can be arbitrarily close to 1. However, explicit bounds for that quantity will be given for inputs with integer coefficients for

6. QR iteration without shift for the Symmetric Eigenvalue Problem.

7. Graeffe iteration for solving univariate polynomials.

The reader should be warned that the results herein are worst case estimates, and are overly pessimistic for application purposes. The main motivation for those results is to convert numerical analysis estimates into ‘polynomial time’ estimates, not the opposite.

2. Statement of main results

Notation. ∥ . ∥_{2} stands for the 2-norm: if x ∈ ℝ^{n} or ℂ^{n}, then

∥ x ∥_{2} = \sqrt{∑_{i=1}^{n} |x_{i}|^{2}} .

If A is a matrix, then

∥ A ∥_{2} = sup_{∥ x ∥_{2} =1} ∥ Ax ∥_{2} .

2.1. Linear equation solving. The first problem considered is linear equation solving: given an n × n matrix A and a vector b ∈ ℝ^{n}, find x ∈ ℝ^{n} such that Ax = b.

Its condition number (with respect to the 2-norm) is defined as

κ(A) = ∥ A ∥_{2} ∥ A^{−1} ∥_{2} .

Comprehensive treatment of the perturbation theory for this problem can be found in the literature, such as [3] Section 2.2, [4] Chapter 7, [14] Lecture 12, etc...

Theorem 1. Let A be an n × n matrix with integer coefficients. If A is invertible, then

κ(A) ≤ n^{\frac{n}{2} +1} (max_{i,j} |A_{ij}|)^{n} .

No originality is claimed for Theorem 1. This result is included for completeness and because its proof is elementary, yet illustrates the principle behind the other results.

2.2. Minimal squares. The second problem in the list is minimal squares fitting. Let A be an m × n matrix, m ≥ n, with full rank, and let b ∈ ℝ^{m}. One has to find x to minimize ∥ Ax − b ∥_{2} ^{2}.

Let r = Ax − b be the residual, we are minimizing ∥ r ∥_{2} ^{2}. Let

sin θ = \begin{matrix}∥ r ∥ & 2 \\ ∥ b ∥ & 2 \end{matrix} .

According to [3] p. 117 (Compare to [14] Lecture 18 and [4] Section 19.1), the condition number of the linear least squares problem is

κ_{LS}(A, b) = \frac{2κ(A)}{cos θ} + tan θ κ(A)^{2} .

Since we do not assume A to be square, we need to give a new definition for κ(A). Let σ_{MAX}(A) and σ_{MIN}(A) be respectively the largest and the smallest singular values of A. Then set

κ(A) = \frac{σ_{MAX}(A)}{σ_{MIN}(A)} .

When m = n, this definition is equal to the previous one.

The singular locus is now the set of pairs (A, b) such that A does not have full rank (i.e. σ_{MIN}(A) = 0) or such that ∥ r ∥_{2} = ∥ b ∥_{2} (i.e. b is orthogonal to the image of A).

The result is:

Theorem 2. Let A be an m × n matrix with integer coefficients, and assume that A has full rank. Let b ∈ ℤ^{m}. Set H = max_{i,j} (|A_{ij}|, |b_{i}|). Then if b is not orthogonal to the image of A, we have:

κ_{LS}(A, b) ≤ 3n^{\frac{n}{2} +1}m^{n+ \frac{1}{2}} H^{2n+1} .

2.3. Non-symmetric eigenvalue problem. Let A be an n × n matrix and let λ be a single eigenvalue of A. The condition number of λ depends on the angle between the left and right eigenvectors:

Let x, y be respectively right and left norm-1 eigenvectors of A associated to λ: Ax = λx, y^{∗}A = λy^{∗}, and ∥ x ∥_{2} = ∥ y ∥_{2} = 1. Then

κ_{NSE}(A, λ) = sec(x̂, y) = \frac{1}{y^{∗}x} .

See [3] Theorem 4.4 p. 149 for references.

Theorem 3. Let A be an n × n matrix with integer coefficients, and let λ be a single eigenvalue of A. Then

κ_{NSE}(A, λ) ≤ n^{3n}2^{2n} (2\sqrt{n}H(A))^{2n^{3}−2n} .

2.4. Solving univariate polynomials. The condition number (in affine space) for solving a univariate polynomial f(x) = ∑_{i=0}^{d} f_{i}x^{i} can be defined ([2] page 228) as:

μ(f) = max_{ζ∈ℂ:f(ζ)=0}μ(f, ζ) ,

where

μ(f, ζ) = \frac{(∑_{i=0}^{d} |ζ|^{2i})^{\frac{1}{2}}}{|f′(ζ)|} .

The degenerate locus is the set of polynomials with a multiple root or with a root at infinity.

Theorem 4. Let f : x ↦ ∑_{i=0}^{d} f_{i}x^{i} be a univariate polynomial with integer coefficients, without multiple roots. Then

μ(f) ≤ 2^{2d^{2}−2}d^{2d} (max |f_{i}|)^{2d^{2}} .

2.5. Solving systems of polynomials. A similar condition number exists for systems of polynomials. However, for the purpose of condition number theory, it is usually convenient to homogenize the equations and to study the perturbation theory of the ‘roots’ in complex projective space. This can also be seen as a change of metric, that simplifies the formula of the condition number and of several theorems (See [2] Chapters 10, 12, 13).

Let f = (f_{1}, ⋯, f_{n}) be a system of polynomials in variables x_{1}, ⋯, x_{n}. We homogenize the system by multiplying each coefficient f_{iJ}x^{J} = f_{iJ}x_{1}^{J_{1}}x_{2}^{J_{2}} ⋯ x_{n}^{J_{n}} of f_{i} by x_{0}^{J_{0}}, where we choose J_{0} = deg f_{i} − (J_{1} + ⋯ J_{n}). We obtain a system of homogeneous polynomials in n + 1 variables, that we call F = (F_{1}, ⋯, F_{n}). The natural space for the roots of F is projective space ℙ^{n}, defined as the space of all ‘rays’

(x_{0} : ⋯: x_{n}) = {(λx_{0}, ⋯, λx_{n}) : λ ∈ ℂ} .

where x_{0}, …, x_{n} are not all equal to 0.

Every finite root (x_{1}, ⋯, x_{n}) of f corresponds to the projective root of F given by (1 : x_{1} : ⋯: x_{n}), and projective roots of F correspond either to a finite root of f or to a root ‘at infinity’.

Suppose that the coefficients of f (hence of F) are made to depend upon a parameter t. The condition number bounds the absolute speed of the roots of F (in projective space) with respect to the absolute speed of the coefficients of F. Recall that the roots ζ of F are in projective space, so their speed vector ζ̇ belongs to the tangent space T_{ζ}ℙ^{n}.

The condition number of F at a root turns out to be:

μ(F, ζ) = ∥ F ∥_{2} ∥ (DF (ζ)_{|T_{ζ}})^{−1} [ \begin{matrix}∥ ζ ∥_{2} & d_{1}−1 \\ & & . & . & . \\ & & & & & ∥ ζ ∥_{2} & d_{n}−1 \end{matrix}] ∥_{2}

where ζ ∈ ℂ^{n+1} is such that (ζ_{0} : ⋯: ζ_{n}) is a root of F (See Proposition 7c in Page 230 of [2]). We did not define the norm of a polynomial yet. Above, ∥ . ∥_{2} stands for the unitary invariant norm (See [15] Chapter III-7 or [2] Section 12.1), that is the most reasonable generalization of the 2-norm to spaces of polynomials:

Notation. Let G be a homogeneous degree d polynomial in n + 1 variables. Then

∥ G ∥_{2} = \sqrt{∑_{J} \frac{|G_{J}|^{2}}{( \begin{matrix}d \\ J \end{matrix} )}}

where ( \begin{matrix}d \\ J \end{matrix} ) is \frac{d!}{J_{0}!···J_{n}!}. Let F be a system of homogeneous polynomials. Then

∥ F ∥_{2} = \sqrt{∑ ∥ F_{i} ∥_{2} ^{2}} .

With these definitions, the number μ(F, ζ) is invariant under scalings of F, ζ, and under the action of the unitary group U(n + 1), where an element Q ∈ SU(n + 1) acts by Q : (F, ζ) ↦ (F ∘ Q, Qζ).

In order to define the condition number of a system of n equations in n variables, we set:

μ(f) = max_{ζ} μ(F, ζ)

where ζ ranges over the roots of F. (Another possibility is to restrict ζ to the nondegenerate roots of F. This would make no difference in this paper). The following theorem is true if one restricts ζ to any subset of the roots of F.

Theorem 5. Let f be a system of n polynomial equations in n variables, with integer coefficients. We write H(f) for the maximum of the absolute value of the coefficients of f, S(f) for the number of non-zero coefficients of f and D for max d_{i}. Assume that μ(f) is finite. Then

μ(f) ≤ ((n + 1)SH(f))^{D^{cn}}

where c is an universal constant.

2.6. Symmetric eigenvalue problem. Let A be an n × n real positive symmetric matrix, and let λ_{1} ≥ λ_{2} ≥ ⋯ λ_{n} ≥ 0 be its eigenvalues.

Unlike the non-symmetric eigenvalue problem, the symmetric eigenvalue problem has absolute condition number always equal to 1 (See [3] Theorem 5.1. See also citePARLETT Fact 1.11 p.16).

However, when using an iterative algorithm, the ratio of eigenvalues

ρ(A) = min_{j>i} \frac{λ_{j}}{λ_{i}}

may play an important role for estimating convergence. For instance, according to [14] Theorem 28.4, the QR algorithm without shift converges linearly with speed \frac{1}{ρ(A)}. Convergence may get slower when ρ(A) → 1. Therefore one can bound the speed of convergence by bounding

ν(A) = ρ(A) − 1 = min_{j>i} \frac{λ_{j} − λ_{i}}{λ_{i}}

above from zero. If ν(A) > δ_{0}, then ρ(A) > 1 + δ_{0}. After k > ⌈\frac{1}{δ_{0}} ⌉ iterations, one gets

ρ(A)^{k} > 1 + kδ_{0} ≥ 2 .

Thus it suffices to perform O(\frac{1}{δ_{0}} log_{2} \frac{1}{δ_{1}} ) iterations to obtain a result with accuracy δ_{1}.

Also, the quantity ν(A)^{−1} can also be interpreted as a condition number for the eigenvectors (See [3] Theorem 5.7 p. 208). We will show here that

Theorem 6. Let A be an n × n matrix with integer coefficients. Then

ν(A)^{−1} ≥ 8^{−n}(4n)^{−n^{2}} (max_{i,j} |A_{ij}|)^{−2n^{2}} .

2.7. Graeffe iteration. Let f : x ↦ ∑_{i=0}^{d} f_{i}x^{i}, f_{d} = 1 be a monic univariate polynomial with zeros ζ_{1}, ⋯, ζ_{d}. Those zeros can be ordered such that

|ζ_{1}| ≥ |ζ_{2}| ≥ ⋯ ≥ |ζ_{d}| .

The Graeffe operator maps the polynomial f(x) = ∏_{i=1}^{d}(x−ζ_{i}) into the polynomial Gf(x) = (−1)^{d}f(\sqrt{x})f(−\sqrt{x}) = ∏_{i=1}^{d}(x − ζ_{i}^{2}).

In [10, 11], it is explained how to recover the actual roots of f after a certain number of Graeffe iterations, with a good approximation. The number of required iterations depends on the ratio:

ρ(f) = max_{|ζ_{j}|>|ζ_{i}|} \frac{|ζ_{j}|}{|ζ_{i}|} .

Unlike in Section 2.6, we do not require here that the roots have different absolute value. We consider also the auxiliary quantity

ν(f) = ρ(f) − 1 = max_{|ζ_{j}|>|ζ_{i}|} \frac{|ζ_{j}| − |ζ_{i}|}{|ζ_{i}|} .

By the above definitions, the ‘condition number’ ν(f)^{−1} is always finite. In order to recover the roots within relative precision δ, the number of Graeffe iterations to perform is

O(log ν(f)^{−1} + log d + log log δ^{−1}) .

For clarity of exposition, we will show that bound under a special hypothesis: all the roots should be different positive real numbers. For the general case, see [8] and [9]. Also, all estimates here are ‘up to the first order’, and quadratic error terms will be discarded.

After k steps of Graeffe iteration one obtains the polynomial

g(x) = G^{k}f(x) = ∑_{i=0}^{d} g_{i}x^{i} = ∏_{i=1}^{d}(x − ζ_{i}^{2^{k}})

with ρ(g) = ρ(f)^{2^{k}}.

Expanding each g_{i} as the (d − i)-th elementary symmetric function of the ζ_{i}^{2^{k}}, one obtains

g_{0} = σ_{d}(ζ_{1}^{2^{k}}, ⋯, ζ_{d}^{2^{k}})
g_{1} = σ_{d−1}(ζ_{1}^{2^{k}}, ⋯, ζ_{d}^{2^{k}})
⋮
g_{d−1} = σ_{1}(ζ_{1}^{2^{k}}, ⋯, ζ_{d}^{2^{k}})
g_{d} = 1

We can use the special hypothesis to bound

(ζ_{1}ζ_{2} ⋯ ζ_{d−i})^{2^{k}} = g_{i}(1 + δ_{i})

with |δ_{i}| < \frac{2^{d}}{ρ(g)} + h.o.t. Hence

ζ_{i}^{2^{k}} = \frac{g_{d−i+1}}{g_{d−i}} (1 + δ′_{i})

with |δ′_{i}| < \frac{2^{d+1}}{ρ(g)} + h.o.t.

Since we assumed the ζ_{i} are all positive, we can recover them by taking 2^{k}-th roots

ζ_{i} = (\frac{g_{d−i+1}}{g_{d−i}} )^{2^{−k}} (1 + δ′′_{i}) .

with |δ′′_{i}| ≤ \frac{2^{d+1−k}}{ρ(g)} + h.o.t.

Now we can use the estimate on ρ(g) = ρ(f)^{2^{k}} to deduce that O(log ν(f)^{−1}+log δ^{−1}) steps are sufficient to obtain a relative precision δ in the roots. Indeed after k_{1} = log_{2} ν(f)^{−1} steps,

ρ(G^{k_{1}}f) = ρ(f)^{2^{log_{2} ν(f)^{−1}}} ≥ 2 .

After extra k_{2} = log_{2}(d + 1 + log_{2} δ^{−1}) steps, one gets

ρ(G^{k_{1}+k_{2}}(f)) > 2^{2^{log_{2}(d+1+log_{2} δ^{−1})}} = 2^{d}δ^{−1} .

So we can set k = k_{1} + k_{2} + 1, the last 1 to get rid of the high order terms, to deduce that |δ′′_{i}| < δ.

Theorem 7. Let f : x ↦ ∑_{i=0}^{d} f_{i}x^{i} be a polynomial with integer coefficients. Then

ν(f)^{−1} > (8 max |f_{i}|)^{−2d} .

This says that Graeffe iteration is ‘polynomial time’, in the sense that we can obtain relative accuracy δ of the roots after

O(d log max |f_{i}| + log log δ^{−1})

steps.

3. Background material

The proof of Theorems 3 to 7 will make use of the absolute multiplicative height function H to bound inequalities involving algebraic numbers.

The construction of the height function H is quite standard in number theory and we refer the reader to [6] Chapter II or to [12] pages 205–214. For applications to complexity theory, see [2] Chapter 7 and [7].

The height function is naturally defined in the projectivization ℙ^{n}(ℚ^{a}) of the algebraic numbers ℚ^{a}. It returns a real number ≥ 1. We can also extend it to complex projective space ℙ^{n} by setting H(P) = ∞ when P ∉ ℙ^{n}(ℚ^{a}). We will adopt this convention in order to simplify the notation of domains and ranges.

Also, if x = (x_{1}, ⋯, x_{n}) ∈ ℂ^{n}, we can define its height as H(x) = H(x_{1} : ⋯: x_{n} : 1).

We can also define the height of matrices, polynomials and systems of polynomials as the height of the vector of all the coefficients.

The following properties of heights will be used in the sequel. First of all, we can explicitly write the height of a vector with integer coefficients as:

Proposition 1. If u ∈ ℤ^{n}, then H(u) = max_{1≤i≤n} |u_{i}|, where | . | is the standard absolute value.

Proposition 1 follows from the construction of the height function. One immediate consequence is that if v ∈ ℚ^{n}, then H(v) = max |mv_{i}|, |m| where m is the greatest common denominator of the v_{i}’s.

We can use the following fact to bound the height of the roots of an integral polynomial:

Proposition 2. If f : x ↦ f(x) = ∑_{i=0}^{d} f_{i}x^{i} is a non-zero polynomial with integer coefficients, and if x is a root of f, then H(x) ≤ 2 max |f_{i}|.

Proposition 2 is Theorem 5 in [7]. Compare with Theorem 5.9 in [12], where the coefficients of f are algebraic numbers.

We can use a bound on the height to bound absolute values above and below:

Proposition 3. Let K be an algebraic extension of ℚ, and let x ∈ K, x ≠ 0. Then

H(x)^{− deg[K:ℚ]} ≤ |x| ≤ H(x)^{deg[K:ℚ]} .

The height of a vector and of its coordinates can be related by:

Proposition 4.

H(x_{1}) ≤ H(x_{1}, ⋯, x_{n}) ≤ H(x_{1})H(x_{2}) ⋯ H(x_{n}) .

Propositions 3 and 4 follow immediately from the construction of the height function. The height function is invariant under permutation of coordinates, and also:

Proposition 5. Let K be an algebraic extension of ℚ, and let g ∈ Gal_{[K:ℚ]}. Then for any x ∈ K, H(g(x)) = H(x)

Proposition 5 is Lemma 5.10 in [12].

Proposition 6. Let

\begin{aligned}F = (F_{0}, ⋯, F_{m}) : & ℂ^{n_{1}} × ℂ^{n_{2}} × ⋯ × ℂ^{n_{k}} & → & ℂ^{m+1} \\ & P^{1}, ⋯, P^{k} & ↦ & F (P^{1}, ⋯, P^{k}) \end{aligned}

be a system of multi-homogeneous polynomials with algebraic coefficients, where each F_{i} has degree d_{j} in variables P^{j}. Let the P^{j} be algebraic. Then

H(F (P)) ≤ (max S(f_{i}))H(F)H(P^{1})^{d_{1}} ⋯ H(P^{k})^{d_{k}} .

In the case k = 1, this is similar to Theorem 5.6 in [12] (where max S(f_{i}) is not given explicitly). For the general case see Theorem 4 in [7].

Proposition 7. Let

\begin{aligned}G = (G_{1}, ⋯, G_{m}) : & ℂ^{n_{1}} × ℂ^{n_{2}} × ⋯ × ℂ^{n_{k}} & → & ℂ^{m} \\ & Q^{1}, ⋯, Q^{k} & ↦ & G(Q^{1}, ⋯, Q^{k}) \end{aligned}

be a system of polynomials with algebraic coefficients, where each G_{i} has degree at most d_{j} in variables Q^{j}. Let the Q^{j} be algebraic. Then

H(G(Q)) ≤ (max S(G_{i}))H(G)H(Q^{1})^{d_{1}} ⋯ H(Q^{k})^{d_{k}} .

This is Corollary 1 in [7]. Some consequences of this are that H(∑_{i=1}^{n} x_{i}) ≤ n ∏ H(x_{i}) and that H(∏_{i=1}^{n} x_{i}) ≤ ∏ H(x_{i}).

The following fact follows also from the construction of heights:

Proposition 8. If x is an algebraic number,

H(x^{2}) = H(x)^{2} .

Also, it makes sense to bound the height of the roots of a system of polynomials with respect to the height, size and degree of the system. Corollary 6 in [5] is:

Proposition 9. [Krick and Pardo] Let f_{1}, ⋯, f_{r} r ≤ n be polynomials in ℤ[x_{1}, ⋯ , x_{r}] of degree and height bounded by d ≥ n and η, respectively, and let V denote the algebraic affine variety defined by: V = {x : f_{1}(x) = ⋯ f_{r}(x) = 0}.

Then V has at most d^{n} isolated points, and their height verifies:

log_{2} H(P) ∈ d^{O(n)}(log_{2} r + log_{2} η) .

4. Proof of Theorems

Notation. If A is a real (resp. complex) matrix, then A^{∗} is the real (resp. complex) transpose of A, (A^{∗})_{ij} = Ā_{ji}. The same convention will be used for vectors.

The vectors of the canonical basis will be denoted by e_{1} = [1, 0, 0, ⋯]^{∗}, e_{2} = [0, 1, 0, ⋯]^{∗}, etc...

4.1. Proof of Theorem 1.

∥ A ∥_{2} = sup_{∥ u ∥_{2} =1} ∥ Au ∥_{2} by definition
≤ ∑_{j} |u_{j}| ∥ [A_{1j}, ⋯, A_{nj}]^{∗} ∥_{2} by triangular inequality
≤ \sqrt{n} max_{j} ∥ [A_{1j}, ⋯, A_{nj}]^{∗} ∥_{2} since ∥ u ∥_{2} =1
≤ n max_{ij} |A_{ij}|

Let A(i, u) be the matrix obtained by replacing the i-th column of A by the vector u. Then if v = A^{−1}u, Cramer’s rule is:

v_{i} = \frac{det A(i, u)}{det A} .

Since A has integer coefficients and det A ≠ 0, one can always bound |v_{i}| ≤ | det A(i, u)|. By Hadamard inequality, this implies:

|v_{i}| ≤ ∥ u ∥_{2} max_{j} ∥ [A_{1j}, ⋯, A_{nj}]^{∗} ∥_{2} ^{n−1}
≤ ∥ u ∥_{2} (\sqrt{n})^{n−1} (max_{i,j} |A_{ij}|)^{n−1}

Therefore,

∥ A^{−1} ∥_{2} = sup_{∥ u ∥_{2} =1} ∥ A^{−1}u ∥_{2} by definition

≤ n^{\frac{n}{2}} (max_{i,j} |A_{ij}|)^{n−1}

Combining the bounds for ∥ A ∥_{2} and ∥ A^{−1} ∥_{2} , one obtains:

κ(A) ≤ n^{\frac{n}{2} +1} (max_{i,j} |A_{ij}|)^{n} .

4.2. Proof of Theorem 2. In order to estimate κ(A), we write

κ(A) = \sqrt{κ(A^{∗}A)}
≤ n^{\frac{n}{4} + \frac{1}{2}} H^{n}m^{n/2}

In order to bound cos θ, we use the assumption that b is not orthogonal to the image of A. Hence ∥ A^{∗}b ∥_{2} ≥ 1 and the ‘normal equation’ A^{∗}Ax = A^{∗}b implies:

∥ A^{∗}Ax ∥_{2} ≥ 1 .

Therefore,

cos θ = \begin{matrix}∥ A^{∗}Ax ∥ & 2 \\ ∥ b ∥ & 2 \end{matrix} ≥ \frac{1}{∥ b ∥_{2}} ≥ \frac{1}{H\sqrt{m}}

and \frac{1}{cos θ} and tan θ are bounded above by H\sqrt{m}. Putting all together,

κ_{LS}(A, b) ≤ 2n^{\frac{n}{4} + \frac{1}{2}} m^{\frac{n}{2} + \frac{1}{2}} H^{n+1} + n^{\frac{n}{2} +1}m^{n+ \frac{1}{2}} H^{2n+1}
≤ 3n^{\frac{n}{2} +1}m^{n+ \frac{1}{2}} H^{2n+1}

4.3. Proof of Theorem 3.

Lemma 1. Let B be an n × n matrix with integer coefficients. Let p(t) = det(B − tI) = ∑ p_{i}t^{i}. Then

max |p_{i}| ≤ (2\sqrt{n} max_{i,j} |B_{ij}|)^{n} .

Proof of Lemma 1.

p_{i} = ∑_{C} ± det C

where C ranges over the (n − i) × (n − i) sub-matrices of B of the form C_{kl} = Bs_{k}s_{l} for some 1 ≤ s_{1} < ⋯ < s_{n−1} ≤ n. Hence

|p_{i}| ≤ ( \begin{matrix}n \\ i \end{matrix} ) max_{C} | det C|

≤ ( \begin{matrix}n \\ i \end{matrix} ) (\sqrt{n − i} max_{ij} |C_{ij}|)^{n−i}
≤ (2\sqrt{n} max_{i,j} |B_{ij}|)^{n}

Lemma 2. Let A be an n × n matrix with integer coefficients and let λ be an eigenvalue of A. Then

H(λ) ≤ 2 (2\sqrt{n} max_{i,j} |A_{ij}|)^{n} .

Proof of Lemma 2. Apply Proposition 2 to the polynomial p(t) from Lemma 1.

Lemma 3. Let B be an n × n matrix with integer coefficients. Let q(t) = det(B − tI + te_{n}^{∗}e_{n}) = ∑ q_{i}t^{i}. Then

max |q_{i}| ≤ 2 (2\sqrt{n} max_{i,j} |B_{ij}|)^{n} .

Proof of Lemma 3. Let p(t) = det(B − tI) and let r(t) = det(B̃ − tI) where B̃ is the (n − 1) × (n − 1) matrix obtained by deleting the n-th row and the n-th column of B. Then, by multi-linearity of the determinant,

p(t) = q(t) ± t r(t) ,

hence

q(t) = p(t) ± t r(t) .

Therefore,

max |q_{i}| ≤ max |p_{i}| + max |r_{i}|
≤ (2\sqrt{n} max_{i,j} |B_{ij}|)^{n} + (2\sqrt{n − 1} max_{i,j} |B_{ij}|)^{n−1} (Lemma 1)
≤ 2 (2\sqrt{n} max_{i,j} |B_{ij}|)^{n}

Lemma 4. Let A be an n × n matrix with integer coefficients. Let λ be an isolated eigenvalue of A and let x be an eigenvector associated to λ, Ax = λx. Then

H(x_{1} : ⋯: x_{n}) ≤ n2^{n} (2\sqrt{n} max_{i,j} |A_{ij}|)^{n^{2}−1} .

Proof of Lemma 4. Assume without loss of generality that the first n − 1 lines of A − λI are independent. Let M_{1}, …, M_{i}, …, M_{n} be the sub-matrices obtained from A − λI by deleting the last line and the i-th column. Then we can scale x in such a way that

x_{i} = ± det M_{i} .

We have M_{n} = B_{n} −λI. By reordering rows and columns, we obtain for each i < n that M_{i} is of the form:

M_{i} = B_{i} − λI + λe_{n−1}^{∗}e_{n−1}

where B_{i} is the sub-matrix of A obtained by deleting the last line and the i-th column. Set q^{(i)}(λ) = det M_{i} = ∑ q_{j}^{(i)}λ^{j}. Now by Lemma 3,

max |q_{j}^{(i)}| ≤ 2 (2\sqrt{n − 1} max_{k,l} |A_{kl}|)^{n−1} .

We consider now the morphism:

\begin{aligned}q : & ℙ & → & ℙ^{n} \\ & (λ : 1) & ↦ & (q^{(1)}(λ) : ⋯: q^{(n)}(λ)) \end{aligned}

Then x = q(λ) and

H(x) = H(q(λ))
≤ nH(q)H(λ)^{n−1}
≤ n2 (2\sqrt{n − 1} max_{i,j} |A_{ij}|)^{n−1} 2^{n−1} (2\sqrt{n} max_{i,j} |A_{ij}|)^{n(n−1)}

≤ n2^{n} (2\sqrt{n} max_{i,j} |A_{ij}|)^{n^{2}−1}

the first inequality because of Proposition 6, and the second because of Lemma 2.

End of the Proof of Theorem 3. Proposition 7 implies

H(y^{∗}x) ≤ nH(x)H(y) .

We claim that deg[ℚ[y^{∗}x] : ℚ] ≤ n. Indeed, x and y can be obtained by solving systems of linear equations with coefficients in ℚ[λ], thus x_{i}, y_{i} ∈ ℚ[λ]. Also, \overline{y_{i}} ∈ ℚ[λ̄] = ℚ[λ] so deg[ℚ[y^{∗}x] : ℚ] ≤ n as claimed.

By hypothesis y^{∗}x ≠ 0. Hence, by Proposition 3,

|y^{∗}x| ≥ (nH(x)H(y))^{−n}
≥ n^{−3n}2^{−2n} (2\sqrt{n} max_{i,j} |A_{ij}|)^{−2n^{3}+2n}

4.4. Proof of Theorem 4.

Proof. According to Proposition 2,

H(ζ) ≤ 2 max |f_{i}| .

Also,

H(f′_{i}) ≤ dH(f) = d max |f_{i}|

and according to Proposition 7

H(f′(ζ)) ≤ dH(f′)H(ζ)^{d−1}
≤ d^{2}2^{d−1}H(f)^{d}

and hence |f′(ζ)| ≥ d^{−2d}H(f)^{−d^{2}}2^{−d(d−1)}. On the other hand,

(∑_{i=0}^{d} |ζ|^{2i})^{\frac{1}{2}} ≤ \sqrt{d + 1} max(1, |ζ|^{d})
≤ \sqrt{d + 1}H(ζ)^{d^{2}}
≤ \sqrt{d + 1}2^{d^{2}}H(f)^{d^{2}}

14 GREGORIO MALAJOVICH^{7}

Hence

μ(f, ζ) ≤ 2^{2d^{2}−2}H(f)^{2d^{2}}d^{2d} .

4.5. Proof of Theorem 5. Lemma 5. Let A be an n × n invertible matrix with algebraic coefficients. Then

H(A^{−1}) ≤ nH(A)^{n} .

Proof of Lemma 5. Let A(i, j) be the sub-matrix of A obtained by deleting the i-th row and the j-th column. By Cramer’s rule, (A^{−1})_{ji} = \frac{det A(i,j)}{det A}. Therefore we should define the degree n morphism:

φ :  ℙ^{n^{2}} → ℙ^{n^{2}}

\begin{matrix}(A_{11} : A_{12} : ⋯ \\ ⋯: A_{nn} : 1) \end{matrix} ↦ (det A(1, 1) : det A(1, 2) : ⋯

⋯: det A(n, n) : det A)

Then by Proposition 6,

H(φ(A)) ≤ n!H(A)^{n}H(φ)
≤ n!H(A)^{n}

Let us fix the notations

M = [ \begin{matrix}∥ ζ ∥_{2} & 1−d_{1} \\ & & . & . & . \\ & & & & & ∥ ζ ∥_{2} & 1−d_{n} \\ & & & & & & & ∥ ζ ∥_{2} & −1 \end{matrix}] [\begin{matrix}DF (ζ) \\ ζ^{∗} \end{matrix}]

and

C = DF (ζ)_{|T_{ζ}}^{−1} [ \begin{matrix}∥ ζ ∥_{2} & d_{1}−1 \\ & & . & . & . \\ & & & & & ∥ ζ ∥_{2} & d_{n}−1 \end{matrix}] .

Let ζ ∈ ℂ^{n+1} be a fixed representative for a root of F. Any u ∈ T_{ζ}ℙ^{n} can be written as a vector in ℂ^{n+1}, orthogonal to ζ. Computing u = Cv is the same as solving Mu = [\begin{matrix}v \\ 0 \end{matrix}]. The operator C is the same as (M^{−1})_{|x_{n+1}=0}. Therefore,

∥ C ∥_{2} ≤ ∥ M^{−1} ∥_{2} .

Lemma 6. In the conditions of Theorem 5, H (M) ≤ S\sqrt{n + 1}^{D−1}H(ζ)^{2D−2}DH(f) .

Proof of Lemma 6. We apply Proposition 7 to the system:

ζ, N ↦ (⋯, N^{d_{i}−1} \frac{∂F_{i}}{∂x_{j}} (ζ), ⋯, ζ̄_{j}, ⋯)

with N = ∥ ζ ∥_{2} ^{−1} to obtain

H(M) ≤ SH(ζ)^{D−1}H(N)^{D−1}H(DF) .

We can bound H(DF) ≤ DH(F) and H(N) = H( ∥ ζ ∥_{2} ) = \sqrt{H(∑ |ζ_{i}|^{2})}. We can apply Proposition 6 to the map

\begin{aligned}φ : & ℂ^{n+1} & → & ℂ \\ & ζ, ζ̄ & ↦ & ∑ ζ_{i}, ζ̄_{i} \end{aligned}

to get H(N^{2}) ≤ (n + 1)H(ζ)H(ζ̄). Proposition 5 implies H(ζ) = H(ζ̄), hence:

H(N^{2}) ≤ (n + 1)H(ζ)^{2}

and by Proposition 8,

H(N) ≤ \sqrt{n + 1}H(ζ) .

Thus, we can estimate that

H(M) ≤ S\sqrt{n + 1}^{D−1}H(ζ)^{2D−2}DH(f) .

End of the Proof of Theorem 5. By definition of the norm, ∥ f ∥_{2} ≤ SH(f). By Lemma 5 and Lemma 6, we have:

H(C) ≤ (n + 1)H(M)^{n}
≤ (n + 1)S^{n}\sqrt{n + 1}^{nD−n}H(ζ)^{2nD−2n}D^{n}H(f)^{n}

Knowing that deg [ℚ[ζ] : ℚ] ≤ D^{n}, we can use Proposition 3 to deduce that

∥ C ∥_{2} ≤ (n + 1)H(C)
≤ (n + 1) ((n + 1)S^{n}\sqrt{n + 1}^{nD−n}H(ζ)^{2nD−2n}D^{n}H(f)^{n})^{D^{n}}

According to Proposition 9,

H(ζ) ≤ nH(f)^{D^{c′n}}

where c′ is a universal constant. Thus,

μ(f, ζ) ≤ SH(f)(n + 1) ((n + 1)S^{n}\sqrt{n + 1}^{nD−n}n^{2nD−2n}
H(f)^{D^{c′n}(2nD−2n)}D^{n}H(f)^{n})^{D^{n}}
≤ ((n + 1)SH(f))^{D^{cn}}

where c is a universal constant.

4.6. Proof of Theorem 6. Lemma 2 implies:

H(λ) ≤ 2 (2\sqrt{n} max_{i,j} |A_{ij})^{n} .

Hence (Proposition 7),

H (\frac{λ_{j}}{λ_{i}} − 1) ≤ 8(4n)^{n} (max_{i,j} |A_{ij}|)^{2n} .

Thus, by Proposition 3,

|\frac{λ_{j}}{λ_{i}} − 1| ≤ 8^{n}(4n)^{n^{2}} (max_{i,j} |A_{ij}|)^{2n^{2}} .

4.7. Proof of Theorem 7. According to Proposition 2,

H(ζ_{i}) ≤ 2H(f)
H(ζ_{j}) ≤ 2H(f)

Moreover, H(|ζ_{i}|) ≤ H(ζ_{i}) because |ζ_{i}|^{2} = ζ_{i}ζ̄_{i} and H(ζ_{i}) = H(ζ̄_{i}) (Propositions 5, 7 and 8). Thus,

H (\frac{|ζ_{j}|}{|ζ_{i}|} − 1) ≤ 2H(|ζ_{i}|)H(|ζ_{j}|)
≤ 8H(f)^{2}

It follows that

ν(f)^{−1} ≥ (8H(f))^{−2 deg[ℚ[|ζ_{i}|,|ζ_{j}|]:ℚ]} ≥ (8H(f))^{−2d} .

5. Further comments

As mentioned before, a reasonable definition for the ‘real complexity’ input size is the number of coefficients of a given problem instance, times the logarithm of its condition number.

Theorems 1 to 4 show that the ‘real complexity’ input size is no worse than a polynomial of the ‘classical complexity’ input size, for problem instances with integer coefficients. Theorem 5 also, if one considers D^{n} as part of the input size. It may be possible to replace D^{n} by the Bézout number ∏ d_{i}, that is the number of solutions of a generic system of polynomials.

Since the ‘real complexity’ of the problems considered can be bound by common numerical analysis techniques, those Theorems provide a scheme to convert ‘real complexity’ bounds into ‘classical complexity’ bounds.

The same idea is behind Theorems 6 and 7. In the case of the iterative algorithms considered, the number of iterations for obtaining a certain approximation can also be bounded in terms of a ‘condition number’. In the case of problem instances with integer coefficients, the ‘condition number’ is also polynomially bounded in terms of the input size.

Those Theorems have many features in common, and this is not a coincidence. A more general approach is to interpret the condition number as the inverse of the distance to the degenerate locus. This can be bounded in terms of the height of the problem instance, and in terms of the degenerate locus (degree, dimension, height). However, bound obtained this way will be no sharper and possibly worse than the direct bounds obtained by using the exact expression for the condition number.

This paper was written while the author was visiting MSRI at Berkeley. He wishes to thank MSRI for its generous support. Thanks to Bernard Deconinck, Jennifer Roveno, Paul Gross, Raquel, and very special thanks to Paulo Ney de Souza and family.

References

[1] Dario Bini and Victor Pan. Polynomial and Matrix Computations, Vol 1. Progress in Theoretical Computer Science. Birkhäuser, Boston, 1994.

[2] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Complexity and Real Computation. Springer, 1998.

[3] James W. Demmel. Applied numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.

[4] Nicholas J. Higham. Accuracy and stability of numerical algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996.

[5] Teresa Krick and Luis M Pardo. A computational method for diophantine approximation. In Proceedings of MEGA’94, Progress in Mathematics. Birkhauser, 1995.

[6] Serge Lang. Survey of Diophantine Geometry. Springer, Berlin, 1997. Corrected Second Printing.

[7] Gregorio Malajovich. On a transfer theorem for the P ≠ N P conjecture, 1998. MSRI Preprint 1998-069.

[8] Gregorio Malajovich and Jorge P. Zubelli. On the geometry of Graeffe iteration, 1997. Informes de Matemática Série B-118, IMPA.

[9] Gregorio Malajovich and Jorge P. Zubelli. Tangent Graeffe iteration, 1998. Informes de Matemática Série B-119, IMPA.

[10] Alexandre Ostrowski. Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent. Acta Math., 72:99–155, 1940.

[11] Alexandre Ostrowski. Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent. Chapitres III et IV. Acta Math., 72:157–257, 1940.

[12] Joseph A. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics 106. Springer, New York, 1986.

[13] Steve Smale. Complexity theory and numerical analysis. Acta Numerica, 6:523–551, 1997.

[14] Lloyd N. Trefethen and David Bau III. Numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.

[15] Hermann Weyl. The Theory of Groups and Quantum Mechanics. Dover Publications, Inc, c.1931, 1951.