Abstract
This paper investigates the solvability of the Absolute Value Equation (AVE) $z - A|z| = b$ using topological degree theory. By introducing the concept of the "aligned spectrum," the authors provide a new framework for determining when a matrix is a $Q$-matrix, ensuring at least one solution for any input vector $b$. The results establish a link between the mapping degree of the AVE function and the number of aligned values exceeding unity, offering a topological generalization of Perron-Frobenius theory to piecewise linear systems.
Introduction
The Absolute Value Equation (AVE), $z - A|z| = b$, is a fundamental problem in mathematical optimization, closely related to the Linear Complementarity Problem (LCP). While the conditions for unique solvability (where $A$ is a $P$-matrix) are well-understood, characterizing general solvability—the property of being a $Q$-matrix—remains a significant challenge. This research addresses the "solvability gap" by employing topological degree theory to analyze the surjectivity of the underlying piecewise linear maps.
Methodology: Topological Degree Theory
The authors model the AVE as a continuous piecewise linear function $F_A(z) = z - A|z|$. The solvability of the equation for any $b$ is equivalent to the surjectivity of $F_A$. According to degree theory, if the mapping degree $\text{deg}(F_A, 0)$ is non-zero, the function is surjective, guaranteeing the existence of at least one solution.
The Aligned Spectrum and Genericity
A central contribution of this work is the definition of the aligned spectrum ($Spec^a(A)$). A value $\lambda$ is defined as aligned if there exists a non-zero vector $x \ge 0$ such that $A|x| = \lambda x$. This concept serves as a refinement of the sign-real spectrum and acts as a piecewise linear analogue to classical eigenvalues.
The analysis focuses on "generic" matrices—those where eigenvalues are simple and eigenvectors do not coincide with the boundaries of coordinate orthants. The authors demonstrate that the mapping degree of $F_A$ is stable and only changes when an aligned value crosses the threshold of 1.
Key Results
The paper establishes several critical theorems relating spectral properties to topological solvability:
- Theorem 1.1 (Degree Parity): For a generic matrix, the mapping degree satisfies $\text{deg}(F_A, 0) \equiv 1 + k \pmod 2$, where $k$ is the number of aligned values greater than 1.
- Corollary 1.3 (Q-matrix Condition): A matrix $A$ is a $Q$-matrix if the number of aligned values greater than 1 is even, as this implies an odd (and thus non-zero) mapping degree.
- Theorem 1.4 (Exact Degree): An exact formula for the degree is provided using the signs of the derivatives of characteristic polynomials at the aligned values.
- Corollary 5.8 (LCP Translation): These results are extended to the LCP, providing a new analytical tool for identifying $Q$-matrices in optimization contexts.
Discussion and Conclusion
By shifting the focus from solution counts to the mapping degree, this research provides a more stable and fundamental indicator of solvability. While the theoretical framework is robust, the authors note that calculating the aligned spectrum is generally NP-hard, posing a challenge for large-scale computational applications. Future work may involve developing algorithms that leverage these topological insights or extending the theory to non-generic, structured matrices common in engineering applications.
Summary updated