Abstract
Given two real vector spaces $U$ and $V$, and a symmetric bilinear map $B: U\times U\to V$, let $Q_B$ be its associated quadratic map. This paper explores three primary computational challenges: (i) determining polynomial-time necessary and sufficient conditions for the surjectivity of $Q_B$; (ii) developing a polynomial-time algorithm for the inversion of $Q_B$ given a point $v \in V$; and (iii) establishing polynomial-time conditions for the indefiniteness of $B$. By reformulating these problems through the geometry of the unprojectivised Veronese surface, the authors bridge the gap between abstract quadratic forms and practical applications in Control Theory.
Introduction
In classical mechanics and control theory, linear approximations are the standard tool for modeling system behavior. However, these models often fail when dealing with "underactuated" systems—such as satellites with limited thrusters or multi-trailer vehicles—where the first-order derivatives do not fully capture the system's reachable states. In such cases, second-order terms, specifically vector-valued quadratic forms, become essential.
While scalar quadratic forms (mapping to $\mathbb{R}$) are well-understood, vector-valued quadratic forms (mapping to a higher-dimensional space $V$) present significant computational hurdles. This paper formalizes the gap in our understanding and proposes a geometric framework to address three fundamental questions regarding these maps.
The Three Core Computational Problems
The authors identify three specific bottlenecks that hinder the application of second-order analysis in control systems:
- Surjectivity: Can the quadratic map $Q_B$ reach every possible point in the target space $V$? Determining if a system can achieve any desired state is a prerequisite for controllability.
- Inversion: If a point $v \in V$ is reachable, can we efficiently (in polynomial time) find an input $u \in U$ such that $Q_B(u) = v$? This is critical for motion planning and trajectory generation.
- Indefiniteness: Is the bilinear map $B$ "indefinite"? This property determines if the map's image is "balanced" or if it is constrained to a specific direction, which has implications for the stability and optimality of the system.
Geometric Interpretation and Methodology
The paper moves beyond abstract algebra by proposing a geometric simplification of these maps. The authors demonstrate that any vector-valued quadratic form can be embedded into the space of symmetric matrices $\text{Sym}_n(\mathbb{R})$.
The Veronese Surface
A key insight is the relationship between the quadratic map and the Veronese surface. The image of $Q_B$ can be viewed as the orthogonal projection of a Veronese surface—a cone of rank-1 matrices—onto a lower-dimensional subspace. This transformation allows researchers to treat surjectivity as a geometric problem: does the projection of this high-dimensional cone "cover" the target subspace?
Trace Decomposition
To further simplify the conditions for surjectivity and indefiniteness, the authors utilize trace decomposition. By splitting the target subspace into a component aligned with the identity matrix and a component consisting of traceless matrices, they provide a more manageable framework for analyzing the map's properties.
Key Results and Propositions
The paper establishes several foundational results that clarify the relationship between the algebraic properties of these maps and their geometric behavior:
- Topological Characterization (Proposition 1): The authors provide a rigorous definition of "indefinite" and "definite" bilinear maps using convex hulls and hyperplanes, grounding these concepts in topology.
- Sufficient Conditions for Surjectivity (Proposition 2): The paper cites a condition based on the "index" of the quadratic form (the number of negative eigenvalues). If this index is sufficiently high relative to the dimension of the target space $V$, surjectivity is guaranteed.
- The 2D Special Case (Proposition 3): In the specific instance where $\dim(U) = \dim(V) = 2$, the authors prove that a symmetric bilinear map is surjective if and only if it is indefinite. This provides a rare, computationally efficient "if and only if" condition.
Discussion: The Complexity Paradox
A significant contribution of this work is the discussion of the "Complexity Paradox." While determining the local controllability of a general nonlinear system is known to be NP-hard, the authors suggest that the specific second-order conditions (the quadratic components) might be solvable in polynomial time. If this hypothesis holds, it would allow for more efficient algorithms in robotics and motion planning, even if the general problem remains difficult.
Conclusion and Future Directions
This paper serves as a call to action for researchers in computational geometry and numerical linear algebra. By formalizing these three open questions, the authors provide a roadmap for developing the next generation of control algorithms. Future work must focus on the discovery of polynomial-time algorithms for checking the surjectivity of the projected Veronese surface in higher dimensions and developing robust inversion techniques for non-holonomic systems.
Summary updated