Note on the Complexity of Some Eigenvector Problems

Thomas Eiter and Georg Gottlob

Christian Doppler Labor für Expertensyteme Technische Universität Wien Paniglgasse 16, 1040 Wien

December 27, 1995

CD-TR 95/89

Note on the Complexity of Some Eigenvector Problems

Thomas Eiter and Georg Gottlob Information Systems Department, TU Vienna Paniglgasse 16, A-1040 Wien, Austria

                  (eiter|gottlob)@dbai.tuwien.ac.at

December 27, 1995

Abstract

We consider the computation of eigenvectors x = (x_{1}, …, n) over the integers, where each component x_{i} satisfies |x_{i}| ≤ c for a constant c. We address decisional problems in this context, and describe some problems complete for NP, Θ_{2}^{p}, F Δ_{2}^{p}, Δ_{2}^{p}, and Σ_{2}^{p}.

1 Introduction and preliminaries

Let R be a ring with 1. Recall that λ ∈ R is an eigenvalue of an n × n matrix M = (m_{i,j}) over R if the equation

M ·x^{T} = λx^{T}

has nontrivial solutions, i.e., solutions x ≠ 0, where x = (x_{1}, …, x_{n}), x^{T} = ( x_{1} ; ⋮ ; x_{n} ) is

the transpose of x, and 0 = (0, …, 0) is the zero vector; all vectors x that satisfy this equation are eigenvectors (for the eigenvalue λ). It is well-known that if R is a field, then the eigenvectors for λ form a vector space, whose dimension is the multiplicity of λ as root of the characteristic polynomial of M. In this short note, we address the computational complexity of some computational problems on eigenvectors. In particular, we consider bounded eigenvectors over the integers, i.e. R = Z. Recall that the norm of an integer vector x, ∥x∥, is defined by ∥x∥ = \sqrt{∑_{i=1}^{n} x_{i}^{2}}. Vector x ∈ V is maximal in a set of vectors V iff ∥y∥ ≤ ∥x∥, for every y ∈ V. We say that vector x is bounded by a number b ≥ 0 (b-bounded) if |x_{i}| ≤ b, for every i = 1, …, n. We consider the following problems (vectors and matrices are tacitly assumed to be over the integers), where c ≥ 1 is a fixed constant:

P1: Given an n × n matrix M, an eigenvalue λ of M, and a real number K, does there exist a c-bounded eigenvector x such that ∥x∥ ≥ K ?

P2: Given an n × n matrix M, an eigenvalue λ of M, and an integer z, decide if there is any maximal eigenvector x among the c-bounded eigenvectors with x_{1} = z, i.e., the first component of x is z.

P3: Given an n × n matrix M and an eigenvalue λ of M, compute the lexicographically first among the maximal c-bounded eigenvectors.

P4: Given an n × n matrix M, an eigenvalue λ of M, a subset I of the components, and an integer z, does there exist a c-bounded ⪯-maximal eigenvector x so that x_{1} = z, where x ⪯ y iff x and y coincide on the components in I and ∥x∥ ⪯ ∥y∥.

Notice that correct problem instances can be recognized in polynomial time, since deciding whether λ is an eigenvalue of M can be done (e.g. using standard Gaussian elimination) in polynomial time.

2 Complexity results

For determining the complexity of problems P1–P4, we refer to variants of problems involving the classical satisfiability problem. Let C be a set of propositional clauses. A truth assignment τ to the variables of C satisfies C, if each clause C contains at least one literal with value true. An assignment τ is not-all-equal satisfying (nae-satisfying) for C, if each clause in C contains two literals that have different value according to τ; clearly, each nae-satisfying assignment of C satisfies C in the standard sense. Moreover, if σ is an nae-satisfying assignment, then also the complementary assignment \overline{σ}, in which each variable has opposite truth value, is nae-satisfying. Let C = {C_{1}, …, C_{m}} be an instance of 3SAT, i.e., a set of propositional clauses C_{i} = α_{i,1} ∨ α_{i,2} ∨ α_{i,3}, i = 1, …, m on variables X = {x_{1}, …, x_{n}}. Then denote by C′ the set of the following clauses:

• x_{j} ∨ x_{j}^{∗} ∨ z_{j} and x_{j} ∨ x_{j}^{∗} ∨ ¬z_{j}, for each j = 1 …, n,

• α_{i,1}^{∗} ∨ α_{i,2}^{∗} ∨ w_{i} and α_{3,i}^{∗} ∨ x_{0} ∨ ¬w_{i}, for each i = 1, …, m

where x_{0}, all z_{j}, all x_{j}^{∗}, and all w_{i} are fresh variables and α_{i,j}^{∗} = x_{ℓ}, if α_{i,j} = x_{ℓ},and α_{i,j}^{∗} = x_{ℓ}^{∗} if α_{i,j} = ¬x_{ℓ}. The following is easily verified. Let τ be an nae-satisfying assignment for C′. If τ(x_{0}) = false, then τ, restricted to X, satisfies C; if τ(x_{0}) = true, then the complementary assignment \overline{τ}, restricted to X, satisfies C. On the other hand, if an assignment σ satisfies C, then σ is extendible to at least one nae-satisfying assignment of C′ in which x_{0} = false. Thus, we obtain the following.

Lemma 2.1 Let C be any instance of 3SAT. The nae-satisfying assignments τ of C′ such that τ(x_{0}) = false, correspond on the variables X 1-1 to the satisfying assignments of C.

As a consequence, deciding whether a SAT instance is satisfiable under nae-satisfaction (NAESAT) is NP-hard [1], even if all clauses have size 3 (NAE3SAT). More general, this allows to conclude that checking the validity of certain Quantified Boolean formulas (QBFs), based on the notion of nae-satisfaction is as hard as for the standard notion of satisfaction. An NAESAT instance C on variables X can be seen as a QBF Φ = ∃XC, where C is viewed as a conjunction of its clauses and the quantifier ∃ ranges over all truth assignments to X. Φ is valid under nae-satisfaction (briefly, nae-valid) if C is a Yes instance. Accordingly, a QBF ∀Y ∃X C where C is in CNF is nae-valid if for every assignment σ to Y, there is an assignment τ to X such that the combined assignment σ ∪ τ nae-satisfies C.

Lemma 2.2 Given a QBF Φ = ∀Y ∃X C, where C is in CNF, deciding whether it is nae-valid is Π_{2}^{p}-complete, and hard even if C is in 3CNF (all clauses have size 3).

Proof. Membership in Π_{2}^{p} is easy: A guess for τ such that no extension of τ by σ does nae-satisfy C can be checked with a call to an NP oracle (the check is in co-NP). Hardness follows from a straightforward reduction of checking the validity of a QBF of the given form in the standard sense, which utilizes the reduction from 3SAT to NAE3SAT given by the transformation from above. I.e., construct for C the formula C′, and consider the QBF Ψ = ∀Y ∃X ∪ X^{∗} ∪ {z_{j}, x_{0}, w_{i}} C′. This formula is nae-valid iff Φ is valid in the standard sense.

Theorem 2.3 Problem P1 is NP-complete, for every fixed c ≥ 1.

Proof. Membership in NP is clear, since a guess for a suitable eigenvector x can be verified in polynomial time. We show hardness by a reduction from NAE3SAT [1], which is, given a 3SAT instance C = {C_{1}, …, C_{M}} on variables X = {x_{1}, …, x_{n}}, decide whether C is nae-satisfiable. We will describe the matrix M in terms of the equations emerging for each component x_{i} from the equation M · x^{T} = λx^{T}; the eigenvalue λ is 1.^{1} That is, we state for each x_{i} the equation

∑_{j=1}^{n} m_{i,j} · x_{j} = x_{i}

Unless stated otherwise, the equation is 1·x_{i} = x_{i} (i.e., the i-th row of M has 1 at column i and 0 everywhere else). We construct a k × k matrix, k = 2n + m, as follows. The components x_{1}, …, x_{n} of an eigenvector x = (x_{1}, …, x_{k}) are supposed to correspond to the variables x_{1}, …, x_{n} of C, and the component values to (partial) truth assignments. For each i = 1, …, n, we have the equation

c·x_{n+i} = x_{i};  (1)

1Here and in the other proofs, we take λ = 1; it is easy to see that 1 is indeed always an eigenvalue of M.

any c-bounded solution requires that (x_{i}, x_{n+i}) is one of (0, 0), (c, 1), (−c, −1). Intuitively, this corresponds to a partial truth assignment, where (c, 1) means that variable x_{i} of C is set true, (−c, −1) that x_{i} is set false, and (0, 0) that x_{i} is undefined. For each clause C_{i} = x_{i_{1}}^{s_{i,1}} ∨ x_{i_{2}}^{s_{i,2}} ∨ x_{i_{3}}^{s_{i,3}} in C, where s_{i,j} ∈ {0, 1} (as usual x^{0} is the literal x and x^{1} the literal ¬x), we have the equation

(−1)^{s_{i,1}} ·x_{i_{1}} + (−1)^{s_{i,2}} ·x_{i_{2}} + (−1)^{s_{i,3}} ·x_{i_{3}} = x_{2n+i}  (2)

The value of x_{2n+i} in any c-bounded eigenvector x is either 0 or ±c. If all literals in C_{i} have assigned a truth value, i.e., x_{i_{j}} = ±c, then x_{2n+i} must have value ±c; this is only possible if two terms (−1)^{s_{i,j}}x_{i_{j}} add up to 0, i.e., the literals corresponding literals L_{j} have opposite value under the truth assignment represented by x. It should be clear from above how the matrix M is completed. Notice that λ = 1 is an eigenvalue of M (e.g., set x_{1} = c and x_{j} = 0, j = 2, …, n, and choose the other components appropriately). Define K = \sqrt{n(c + 1) + m·c}. It is easy to see that the instance M, λ, K of P1 is a Yes-instance iff C is nae-satisfiable. This proves the result.

Remark. Problem P1 remains in NP also if c is not fixed, but a number in the input.

Theorem 2.4 Problem P2 is Θ_{2}^{p}-complete, for every fixed c ≥ 1. Hardness holds even for z = 0.

Proof. The problem can be solved with a logarithmic number of queries to an NP oracle, by computing first the norm δ of a maximal c-bounded eigenvector in binary search (cf. problem P1; note that δ ≤ c^{2}·n, and the input size is larger than n) and then querying the oracle whether there exists a c-bounded eigenvector x such that ∥x∥ = δ and x_{1} = z. Hardness is shown by a reduction from the following problem. Consider the variant of NAE3SAT in which it is known that C is nae-satisfied by a certain assignment τ in which τ(x_{1}) = τ(x_{2}); deciding whether there is an nae-satisfying assignment for C in which τ(x_{1}) ≠ τ(x_{2}) is NP-complete. Therefore, by the results in [3], given k instances C^{1}, …, C^{k} of this problem (on different variables), deciding whether the number of Yesinstances is even is Θ_{2}^{p}-complete. We reduce this problem to P2 as follows. For each instance C^{i} on variables X^{i} = {x_{1}^{i}, …, x_{n_{i}}^{i}}, we use the equations of the transformation of NAE3SAT to P1 in the proof of Theorem 2.3;^{2} note that an eigenvector of respective norm K^{i} always exists. Furthermore, we add for C^{i} equations

1·x_{s}^{i} + 1·x_{t}^{i} = x_{t}^{i}
1·x_{n+1}^{i} + (−1)·x_{n+2}^{i} + 2·x_{r}^{i} = x_{s}^{i}

where x_{r}^{i}, x_{s}^{i}, and x_{t}^{i} are new variables. Clearly, x_{s}^{i} = 0 in any eigenvector, and x_{t}^{i} = ±c in any maximal eigenvector. Since x_{n+1}^{i} and x_{n+2}^{i} have in any eigenvector values from −1, 0, 1, x_{r}^{i} has either value 0, 1, or −1. Moreover, for each variable x_{2n_{i}+j}^{i} introduced for the clause C_{j}^{i} on the right hand side of equation 2, take a new variable x_{2n_{i}+j}^{′i} that is set to the same value, i.e., add the equation

2Here and in the rest of the paper, for better readability we use component names x_{j}^{i}, y_{i}, etc which can be easily transformed to names x_{1}, …, x_{n} as stated in problems P1–P4.

1·x_{2n_{i}+j}^{i} = x_{2n_{i}+j}^{′i}

If C^{i} is a Yes-instance, then all maximal c-bounded eigenvectors x have x_{r}^{i} = ±1 and norm \sqrt{n(c + 1) + 2·c·m + c + 1}; if C^{i} is not a Yes-instance, then they have x_{r}^{i} = 0 and norm \sqrt{n(c + 1) + 2·c·m + c}. To combine the instances C^{i}, introduce for each variable x occurring so far fresh variables p_{1}, …, p_{ℓ}, where ℓ = ⌈c⌉, that are equated to x, i.e., satisfy

1·x = p_{j},  j = 1, …, ℓ  (3)

and set up the equations

1·x_{s} + 1·x_{t} = x_{t}  (4)
c·x_{r}^{1} + ⋯ + c·x_{r}^{k} + 1·x_{r} = x_{s}  (5)

where x_{r}, x_{s}, and x_{t} are new variables. The value of x_{s} in any eigenvector is 0, and x_{t} = ±c in every maximal c-bounded eigenvector; since the value of x_{r}^{i} is from 0, −1, 1, the value of x_{r} is from −c, 0, c. If the number of Yes-instances among C^{1}, …, C^{k} is odd, then x_{r} = ±c, and if it is even, then x_{r} = 0. (Note that if x is an eigenvector, so is (−1)x; hence, the x_{r}^{i} with value ≠ 0 can be chosen so that they pairwise cancel.) Indeed, in each maximal eigenvector x_{r}^{i} = 0 if C^{i} is not a Yes-instance, and x_{r}^{i} = ±1 if C^{i} is a Yes-instance. The variable copies p_{i} assure that for every C^{i}, taking the right x_{r}^{i} has a larger global influence on the norm of a maximal eigenvector than x_{r}, which will be set according to whether the number of x_{r}^{i}’s ≠ 0 is odd or not. Thus, deciding whether some maximal c-bounded eigenvector exists for M, λ = 1 such that x_{r} = 0, is Θ_{2}^{p}-hard. By reordering the components such that x_{r} is the first, this proves the result.

Recall that a truth assignment τ to the variables x_{1}, …, x_{n} is lexicographically smaller than a truth assignment σ, if τ(x_{i}) = false for the least index i such that τ(x_{i}) ≠ σ(x_{i}).

Lemma 2.5 Given an NAE3SAT instance C, computing the lexicographically first naesatisfying assignment of C, τ^{∗}, is FΔ_{2}^{p}-complete, as is computing τ^{∗}(x_{i}) for any given variable x_{i}. This holds even if C is known to be nae-satisfiable.

Proof. Reduce the analogous problem for 3SAT, and using the transformation of a 3SAT instance C to a NAE3SAT instance C′ described above Lemma 2.1. Then, order the variables arbitrarily but so that the order starts with x_{0}, x_{1}, …, x_{n}. By Lemma 2.1, the lexicographic first nae-satisfying assignment of C′ corresponds to the lexicographic first assignment of C. Computing the latter, as well as a given bit thereof, is well-known FΔ_{2}^{p}-complete [2]. This proves hardness. Membership is clear, as for each component only constantly many values have to be considered, and deciding if a partial vector can be completed to a c-bounded eigenvector is obviously in NP.

Theorem 2.6 Problem P3 is FΔ_{2}^{p}-complete, for every fixed c ≥ 1.

Proof. Membership is straightforward: the norm of a maximal c-bounded eigenvector, δ, can be computed in polynomial time with a logarithmic number of calls to an NP-oracle (query instances of P1); computing the lexicographically first eigenvector x^{∗} of norm δ can be done with a linear number of NP oracle calls, computing x_{1}^{∗}, x_{2}^{∗} and so on in order; for each component x_{i} only a constant number of values are possible, and deciding if a partial vector x_{1}, …, x_{k} can be completed to a c-bounded eigenvector with norm δ is in NP. To show hardness, use the same reduction as in the proof of Theorem 2.3. Under the assumption that C is nae-satisfiable, δ takes the value K = n(c + 1) + m·n, which is the largest possible value. Therefore, maximal eigenvectors correspond to nae-satisfying assignments of C. In particular, the lexicographically first maximal c-bounded eigenvector (in which x_{0} = −c) corresponds to the lexicographically first nae-satisfying assignment of C (in which x_{0} = false).

Corollary 2.7 Let c ≥ 1 be fixed. Given an n × n matrix M, an eigenvalue λ of M, and integers i, z, deciding if x_{i} = z for the lexicographically first maximal eigenvector x among those that are c-bounded is Δ_{2}^{p}-complete.

Proof. Deciding any given bit of the lexicographically first satisfying truth assignment is Δ_{2}^{p}-complete [2]. Thus, the result follows from the proof of Theorem 2.6.

Theorem 2.8 Problem P4 is Σ_{2}^{p}-complete, for every fixed c ≥ 1. Hardness holds for z = 0.

Proof. The problem is in Σ_{2}^{p}, since a guess for a ⪯-maximal c-bounded eigenvector x can be verified with a single call to an NP oracle (deciding whether a vector y ⪯ x with x ≠ y exists is in NP). Hardness is shown by using a slight variant of the problem in Lemma 2.2. It is assumed that for each assignment σ to Y, a particular assignment τ to all variables X exists in which τ(x_{1}) = τ(x_{2}) such that σ∪τ nae-satisfies C; it is asked whether a τ exists such that σ ∪ τ nae-satisfies C and τ(x_{1}) ≠ τ(x_{2}). This problem is easily shown to be Π_{2}^{p}-complete. We reduce this problem to the complement of P4. Let the input be the formula Φ = ∀Y ∃X C. For the formula C, seen as an NAE3SAT instance on variables Y ∪ X, set up the same equations as in the reduction of NAE3SAT to P1 described in the proof of Theorem 2.3. Furthermore, add the equations

1·x_{s} + 1·x_{t} = x_{t}  (6)
1·x_{1} + (−1)·x_{2} + 2c·x_{r} = x_{s},  (7)

where x_{r}, x_{s}, and x_{t} are new variables; take for each x_{2n+i} that was introduced for clause C_{i} (cf. eq. (2)) a fresh variable x′_{2n+i} and equate it to x_{2n+i}, i.e., set up

1·x_{2n+i} = x′_{2n+i}.  (8)

Recall that x_{1} and x_{2} have in any eigenvector values from −1, 0, 1; thus, x_{r} has value 0 if x_{1} = x_{2} and value ±1 if x_{1} ≠ x_{2}. Consider for the moment eigenvectors in which each y_{i} from Y has value ±c; this represents a truth assignment σ to the variables in Y, where σ(y_{i}) = true iff y_{i} = c, and σ(y_{i}) = false iff y_{i} = −c. The assumption on Φ entails the following for every ⪯-maximal eigenvector x corresponding to σ. If σ can not be extended by some τ to an nae-satisfying assignment for C in which τ(x_{1}) ≠ τ(x_{2}), then x has norm \sqrt{n(c + 1) + 2·c·m + c} and x_{r} = 0 (n = |Y ∪ X|); if σ is extendible by such a τ, then x has norm \sqrt{n(c + 1) + 2·m·c + 1} and x_{r} = ±1. Therefore, if we only consider eigenvectors in which each y_{i} is assigned a truth value and choose for I the set Y, a ⪯-maximal such vector exists in which x_{r} = 0, precisely if for the assignment to the y_{i} variables represented by this vector, every assignment τ to the x_{i} variables in which τ(x_{1}) ≠ τ(x_{2}) does not nae-satisfy C. However, we have also to take into account ⪯-maximal eigenvectors in which some y_{i} might have value 0. To handle this, we introduce for each variable y_{i} three new variables p_{i}, p′_{i} and p′′_{i}, and set up the equations

c·p′_{i} = p_{i}
p_{i} + (−1) · y_{i} = p′′_{i};

for I, we choose the set of components p_{i}. The value of p_{i} is in each eigenvector from 0, −c, c; consider a ⪯-maximal such vector. If p_{i} = 0, then, as easy to see, y_{i} has value ±c and p′′_{i} has value ∓c. Otherwise, if p_{i} = ±c, then y_{i} = p_{i} must hold. Therefore, each ⪯-maximal eigenvector represents a total truth assignment σ to the variables Y; moreover, it has x_{r} = 0 iff an assignment τ to the variables X exists, where τ(x_{1}) ≠ τ(x_{2}), such that σ ∪ τ nae-satisfies C (in fact, such a τ is encoded by the vector). Now reorder the components such that x_{r} becomes the first. Then, the instance of P4 where M is as obvious, λ = 1, I = {p_{i}} and z = 0, is not a Yes instance iff the formula Φ is valid under nae-satisfaction. This proves the result.

References

[1] M. Garey and D. S. Johnson. Computers and Intractability – A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.

[2] M. Krentel. The Complexity of Optimization Problems. Journal of Computer and System Sciences, 36:490–509, 1988.

[3] K. Wagner. Bounded Query Classes. SIAM J. Comp., 19(5):833–846, 1990.