A necessary and sufficient condition for parameter insensitive disturbance-rejection problem with state feedback

In this paper a necessary and sufficient condition for a parameter insensitive disturbance-rejection problem with state feedback which was pointed out as an open problem by Bhattacharyya to be solvable is proved. A constructive algorithm of simultaneously (A,B)-invariant subspaces for a finite-number of linear systems and a relationship between simultaneously (A,B)-invariant subspaces and generalized (A,B)-invariant subspaces play an important role to prove the main result.     

Applications of dimensionality reduction and exponential sums to graph automorphism

Given a connected undirected graph, we associate a simplex with it such that two graphs are isomorphic if and only if their corresponding simplices are congruent under an isometric map. In the first part of the paper, we study the effectiveness of a dimensionality reduction approach to Graph Automorphism. More precisely, we show that orthogonal projections of the simplex onto a lower dimensional space preserves an automorphism if and only if the space is an invariant subspace of the automorphism. This insight motivates the study of invariant subspaces of an automorphism. We show the existence of some interesting (possibly lower dimensional) invariant subspaces of an automorphism. As an application of the correspondence between a graph and its simplex, we show that there are roughly a quadratic number of invariants that uniquely characterize a connected undirected graph up to isomorphism.In the second part, we present an exponential sum formula for counting the number of automorphisms of a graph and study the computation of this formula. As an application, we show that for a fixed prime p and any graph G, we can count, modulo p, the number of permutations that violate a multiple of p edges in G in polynomial time.     

Geometric state-space theory in linear multivariable control: A status report

With the renewed emphasis in control theory on qualitative structural issues, as distinct from techniques of optimization, the last decade has brought significant growth in the application of geometric ideas to the formulation and solution of problems of controller synthesis. In this article we review the status of geometric state space theory as developed for application to systems that are linear, multivariable and time-invariant. After a brief summary of the underlying geometric concepts ((A, B)-invariant subspaces and (A, B)-controllability subspaces) we outline two standard problems of feedback control that have been successfully attacked from this point of view, and briefly survey recent results in a range of other topic areas. Then we discuss certain issues of methodology, and conclude with some remarks on computational procedures.     

Necessary and sufficient conditions for existence of J-spectral factorization for para-Hermitian rational matrix functions

For a para-Hermitian rational matrix function G(λ)=J+C(λI_p−A)⁻¹B, where J=J∗ is invertible, and which has no poles and zeros on the imaginary line, we give necessary and sufficient conditions in terms of A,B,C and J for the existence of a J-spectral factorization, as well as an algorithm to obtain the J-spectral factor in case it exists.     

Tableau methods for analysis and design of linear systems

Certain classes of elementary operations on the system matrix of a linear system are defined, and then their use is illustrated for the calculation of canonical forms, the largest (A,B)-invariant and controllability subspaces in ker(C), transmission zeros, and minimal inverses. Questions of numerical accuracy are discussed. The results are directly codable as efficient numerical algorithms, and may be extended to the use of orthogonal transformations.     

Invariance and polynomial design of strategies in the linear-quadratic game

A new algorithm to solve the H ^∞ control problem in the case of full information was presented. It combines the spectral and matrix methods. The polynomial Lur’e-Riccati operator was introduced. Parametrization of all solutions of the controlled plant equation by hidden variables was presented within the framework of the J.C. Willems behavioral approach. The kernel of the polynomial Lur’e-Riccati operator was decomposed into the direct sum of subspaces that are similar to the Jordan blocks. The saddle point of the linear-quadratic game which was found by V.A. Yakubovich in 1970 was shown to provide solution to the H ^∞ control problem for a considerable class of controlled plants.     

Geometric criteria for controllability and near-controllability of driftless discrete-time bilinear systems

Geometric approaches have been well developed for both linear and nonlinear systems, which are useful in the analysis and design of control systems. However, geometric approaches have been less considered for discrete-time bilinear systems. In this paper, controllability and near-controllability of driftless discrete-time bilinear systems are dealt with from a geometric point of view. More specifically, geometric characterizations are presented for controllability and near-controllability as well as for controllable subspaces and nearly controllable subspaces of the systems. Differently from the classical geometric approach for linear systems, it is shown that, for the bilinear systems, a controllable subspace has to be determined by two linear subspaces, while a nearly controllable subspace is determined by one linear subspace. As a result, geometric criteria for controllability, near-controllability, controllable subspaces, and nearly controllable subspaces of the systems are respectively derived, which are also applied to multi-input discrete-time bilinear systems and to linear time-invariant systems with a multiplicative perturbation. Examples are given to illustrate the derived geometric criteria.     

Strong NP-completeness of a matrix similarity problem

Consider the following problem: given an upper triangular matrix A, with rational entries and distinct diagonal elements, and a tolerance τ ⩾ 1, decide whether there exists a nonsingular matrix G, with condition number bounded by τ, such that G⁻¹AG is 2 × 2 block diagonal. This problem, which we shall refer to as DICHOTOMY, is an important one in the theory of invariant subspaces. It has recently been proved that DICHOTOMY is NP-complete. In this note we make some progress proving that DICHOTOMY is actually NP-complete in the strong sense. This outlines the “purely combinatorial” nature of the difficulty, which might well arise even in case of well scaled matrices with entries of small magnitude.     

Detection filter design for LPV systems—a geometric approach

This paper investigates fault detection and isolation of linear parameter-varying (LPV) systems by using parameter-varying (C,A)-invariant subspace and parameter-varying unobservability subspaces. The so called “detection filter” approach, formulated as the fundamental problem of residual generation (FPRG) for linear time-invariant (LTI) systems, is extended for a class of LPV systems. The question of stability is addressed in the terms of Lyapunov quadratic stability by using linear matrix inequalities. The results are applied to the model of a generic small commercial aircraft.     

On the geometry of symplectic pencils arising from discrete-time matrix equations

In this paper general symplectic matrix pencils are considered disregarding the particular matrix equations from which they arise. A parameterization of the Lagrangian deflating subspaces is given with the only assumption of regularity of the matrix pencil.     

Stability radius optimization: A geometric approach

The subject of this paper is a geometric approach to the robustness optimization problem for uncertain finite dimensional linear systems. For the structurally perturbed stabilizable pair (A, B), we show that optimally robust feedback stabilization is possible via the class of feedbacks parameterizing (A, B) feedback invariant subspaces of codimension Rk B. A direct consequence of this geometric approach is a reduction in dimension of the optimization problem.     

Two simple and efficient algorithms for Jordan sorting and polygon cutting and clipping

This paper deals with the Jordan sorting problem: Given n intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, sort these points into the order in which they occur along the x-axis. The worst-case time complexity of this problem is θ(n). Unfortunately, the known O(n) time algorithms are too complicated, which causes that they are difficult to implement and slow for the inputs of sizes that are of practical interest. In this paper, two algorithms for Jordan sorting are presented. The first algorithm is extremely simple. Although its worst-case time complexity is O(nlogn), it is shown that the worst time is achieved only for special inputs. For most inputs, a better performance can be expected. Furthermore, an improved O(nlog logn) worst-case time algorithm is presented. For the input sequences of size from 4 to 10⁵, the algorithms are compared with Quicksort, with the algorithm based on splay trees and with the O(n) time algorithm proposed by Fung et al. The results show that our algorithms are faster. The relevant implementation details are given.     

Observing linear dynamics with polynomial output functions

We address the problem of observing a linear system by a scalar polynomial output function. We show that if the null space of A has dimension at most one, then one can always find such an output function which observes the system and when all the eigenvalues of A are real, then a necessary condition for the observability of the system is that the degree of the polynomial is greater than a certain integer which is related to the maximum number of Jordan blocks corresponding to any eigenvalue.     

Structural synthesis of multivariable controllers

In this paper the problem of achieving a desired transfer function matrix H_d(s) between external inputs and controlled outputs in a linear multivariable system by connecting proper, stabilizing controllers between measured outputs and control inputs is solved in both transfer function and state space settings. The class H_d of achievable transfer functions is directly and constructively characterized via the theory of transfer function valuations. For each H_d(s)ϵH_d, the class of synthesizing controllers is determined. Similar valuation conditions are given for the asymptotic tracking and disturbance rejection problem in which H_d(s) is only partially specified. These results extend and complement earlier results. The state space geometric solution of the problem of achieving a desired H_d(s) is obtained by formulating it as an equivalent output feedback disturbance rejection problem. A constructive solvability condition in terms of a pair of measurement and control invariant subspaces is given. This requires a nontrivial generalization of the notion of (C, A, B) pairs. An H_d(s) is shown to be admissible if and only if it induces an appropriate pair of invariant subspaces. The signal flow structure and certain factorizability conditions for a robust synthesis of the output feedback disturbance rejection problem are also given which extend earlier results on robust state feedback disturbance rejection. It is shown that every compensator corresponds to a state feedback control law implemented by an unknown input observer. The results of this paper are expected to be useful in the development of parameter optimization or other computer aided design algorithms where response specifications are to be traded against other design criteria such as sensitivity or stability margins since they explicitly characterize the algebraic variety H_d in which the response transfer function may lie.     

Mitigation of symmetry condition in positive realness for adaptive control

Feasibility of nonlinear and adaptive control methodologies in multivariable linear time-invariant systems with state-space realization {A,B,C} is apparently limited by the standard strictly positive realness conditions that imply that the product CB must be positive definite symmetric. This paper expands the applicability of the strictly positive realness conditions used for the proofs of stability of adaptive control or control with uncertainty by showing that the not necessarily symmetric CB is only required to have a diagonal Jordan form and positive eigenvalues. The paper also shows that under the new condition any minimum-phase systems can be made strictly positive real via constant output feedback. The paper illustrates the usefulness of these extended properties with an adaptive control example.     

Variations of α and G from nonlinear multidimensional gravity

To explain the recently reported large-scale spatial variations of the fine structure constant α, we apply some models of curvature-nonlinear multidimensional gravity. Under the reasonable assumption of slow changes of all quantities as compared with the Planck scale, the original theory reduces to a multiscalar field theory in four dimensions. On this basis, we consider different variants of isotropic cosmological models in both the Einstein and Jordan conformal frames. One of the models turns out to be equally viable in both frames, but in the Jordan frame themodel predicts simultaneous variations of α and the gravitational constant G, equal in magnitude. Large-scale small inhomogeneous perturbations of these models allow for explaining the observed distribution of α values.     

Feedback invariants of supplementary pairs of matrices

Given a pair of matrices (A,B), with every (A,B)-invariant subspace and the corresponding supplementary sub-space we can associate pairs (A₁,B₁) and (A₂, B₂) which identify them up to feedback equivalence. A complete characterization of the controllability indices of (A,B) in terms of those of (A₁,B₁), (A₂, B₂) is provided under the assumption of complete controllability of (A₁,B₁). This problem is related to the feedback simulation problem.     

Short rational functions for toric algebra and applications

We encode the binomials belonging to the toric ideal I_A associated with an integral d×n matrix A using a short sum of rational functions as introduced by Barvinok (Math. Operations Research 19 (1994) 769) and Barvinok and Woods (J. Amer. Math. Soc. 16 (2003) 957). Under the assumption that d and n are fixed, this representation allows us to compute a universal Gröbner basis and the reduced Gröbner basis of the ideal I_A, with respect to any term order, in time polynomial in the size of the input. We also derive a polynomial time algorithm for normal form computations which replaces in this new encoding the usual reductions typical of the division algorithm. We describe other applications, such as the computation of Hilbert series of normal semigroup rings, and we indicate applications to enumerative combinatorics, integer programming, and statistics.