Solvability of orbit-finite systems of linear equations
We study orbit-finite systems of linear equations, in the setting of sets with atoms. Our principal contribution is a decision procedure for solvability of such systems. The procedure works for every field (and even commutative ring) under mild effectiveness assumptions, and reduces a given orbit-finite system to a number of finite ones: exponentially many in general, but polynomially many when atom dimension of input systems is fixed. Towards obtaining the procedure we push further the theory of vector spaces generated by orbit-finite sets, and show that each such vector space admits an orbit-finite basis. This fundamental property is a key tool in our development, but should be also of wider interest.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the solvability of weakly linear systems of fuzzy relation equations
Systems of fuzzy relation equations and inequalities in which an unknown fuzzy relation is on the one side of the equation or inequality are linear systems. They are the most studied ones, and a vast literature on linear…
RelationViewing Graph Solvability via Cycle Consistency
In structure-from-motion the viewing graph is a graph where vertices correspond to cameras and edges represent fundamental matrices. We provide a new formulation and an algorithm for establishing whether a viewing gr…
Viewing Graph Solvability in Practice
We present an advance in understanding the projective Structure-from-Motion, focusing in particular on the viewing graph: such a graph has cameras as nodes and fundamental matrices as edges. We propose a practical me…
Nominal Topology for Data Languages
We propose a novel topological perspective on data languages recognizable by orbit-finite nominal monoids. For this purpose, we introduce pro-orbit-finite nominal topological spaces. Assuming globally bounded support siz…
Lyapunov equations: a (fixed) point of view
The Lyapunov equation is the gateway drug of nonlinear control theory. In these notes we revisit an elegant statement connecting the concepts of asymptotic stability and observability, to the solvability of Lyapunov equa…