Scattering Systems with Several Evolutions and Multidimensional Input/State/Output Systems

The one-to-one correspondence between one-dimensional linear (stationary, causal) input/state/output systems and scattering systems with one evolution operator, in which the scattering function of the scattering system coincides with the transfer function of the linear system, is well understood, and has significant applications in H^∞ control theory. Here we consider this correspondence in the d-dimensional setting in which the transfer and scattering functions are defined on the polydisk. Unlike in the onedimensional case, the multidimensional state space realizations and the corresponding multi-evolution scattering systems are not necessarily equivalent, and the cases d = 2 and d > 2 differ substantially. A new proof of Andô’s dilation theorem for a pair of commuting contraction operators and a new statespace realization theorem for a matrix-valued inner function on the bidisk are obtained as corollaries of the analysis.     

Nonlinearity inH ∞-control theory,causality in the commutant lifting theorem,and extension of intertwining operators

The problems studied in this note have been motivated by our work in generalizing linearH control theory to nonlinear systems. These ideas have led to a design procedure applicable to analytic nonlinear plants. Our technique is a generalization of the linearH theory. In contrast to previous work on this topic ([9], [10]), we now are able to explicitly incorporate a causality constraint into the theory. In fact, we show that it is possible to reduce a causal optimal design problem (for nonlinear systems) to a classical interpolation problem solvable by the commutant lifting theorem [8]. Here we present the complete operator theoretical background of our research together with a short control theoretical motivation.This work was supported in part by grants from the Research Fund of Indiana University, the National Science Foundation DMS-8811084 and ECS-9122106, by the Air Force Office of Scientific Research F49620-94-1-0098DEF, and by the Army Research Office DAAL03-91-G-0019 and DAAH04-93-G-0332     

Approximate controllability of a class of semilinear degenerate systems with boundary control

This paper concerns a class of control systems governed by semilinear degenerate equations with boundary control in one-dimensional space. The control is proposed on the ‘degenerate’ part of the boundary. The control systems are shown to be approximately controllable by Kakutani's fixed point theorem.     

Matching Polynomials And Duality

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.     

Hierarchical decomposition of symmetric discrete systems by matroid and group theories

An algebraic method is proposed for the hierarchical decomposition of large-scale group-symmetric discrete systems into partially ordered subsystems. It aims at extracting substructures and hierarchy for such systems as electrical networks and truss structures.The mathematical problem considered is: given a parametrized family of group invariant structured matricesA, we are to find two constant (=parameter-independent) nonsingular matricesS _r andS _c such thatS _r ^-1 AS _c takes a (common) block-triangular form.The proposed method combines two different decomposition principles developed independently in matroid theory and in group representation theory. The one is the decomposition principle for submodular functions, which has led to the Dulmage—Mendelsohn (DM-) decomposition and further to the combinatorial canonical form (CCF) of layered mixed (LM-) matrices. The other is the full reducibility of group representations, which yields the block-diagonal decomposition of group invariant matrices. The optimality of the proposed method is also discussed.     

Independence numbers of graphs and generators of ideals

This article investigates the generators of certain homogeneous ideals which are associated with graphs with bounded independence numbers. These ideals first appeared in the theory oft-designs. The main theorem suggests a new approach to the Clique Problem which isNP-complete. This theorem has a more general form in commutative algebra dealing with ideals associated with unions of linear varieties. This general theorem is stated in the article; a corollary to it generalizes Turán’s theorem on the maximum graphs with a prescribed clique number. Research supported in part by NSF Grant MCS77-03533.     

Point Evaluation and Hardy Space on a Homogeneous Tree

We consider stationary multiscale systems as defined by Basseville, Benveniste, Nikoukhah and Willsky. We show that there are deep analogies with the discrete time non stationary setting as developed by the first author, Dewilde and Dym. Following these analogies we define a point evaluation with values in a C*–algebra and the corresponding “Hardy space” in which Cauchy’s formula holds. This point evaluation is used to define in this context the counterpart of classical notions such as Blaschke factors.     

On causality in commutant lifting theorem. I

Two functionals (A) and for an operatorA were introduced in [11] for the study of causality in commutant lifting theory. In this paper we give sufficient and necessary conditions for in a special case. We prove that in this case , and we show by some examples related to nonlinear system control that is the best constant in our inequality.     

OnJ-conservative scattering system realizations in several variables

We prove that an arbitrary function, which is holomorphic on some neighbourhood ofz=0 in ^N and vanishes atz=0, and whose values are bounded linear operators mapping one separable Hilbert space into another one, can be represented as the transfer function of some multi-parameter discrete time-invariant conservative scattering linear system whose state space is a Krein space.The author is thankful to Prof. D.Z. Arov for suggesting this problem. He wishes also to thank Leeds University, where the revised version of this paper was prepared, for its hospitality, and Dr. V.V. Kisil who organized his visit there under the International Short Visits Scheme of LMS (grant no. 5620).     

Boundary controllability of a linear semi-discrete 1-D wave equation derived from a mixed finite element method

In this article one discusses the controllability of a semi-discrete system obtained by discretizing in space the linear 1-D wave equation with a boundary control at one extremity. It is known that the semi-discrete models obtained with finite difference or the classical finite element method are not uniformly controllable as the discretization parameter h goes to zero (see [8]). Here we introduce a new semi-discrete model based on a mixed finite element method with two different basis functions for the position and velocity. We show that the controls obtained with these semi-discrete systems can be chosen uniformly bounded in L²(0,T) and in such a way that they converge to the HUM control of the continuous wave equation, i.e. the minimal L²-norm control. We illustrate the mathematical results with several numerical experiments. Supported by Grant BFM 2002-03345 of MCYT (Spain) and the TMR projects of the EU ``Homogenization and Multiple Scales" and ``New materials, adaptive systems and their nonlinearities: modelling, control and numerical simulations". Partially Supported by Grant BFM 2002-03345 of MCYT (Spain), Grant 17 of Egide-Brancusi Program and Grant 80/2005 of CNCSIS (Romania).     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

Maximum degree and fractional matchings in uniform hypergraphs

Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.     

Temperely-Lieb Algebras and the Four-Color Theorem

The Temperley–Lieb algebra T_n with parameter 2 is the associative algebra over Q generated by 1,e₀,e₁, . . .,e_n, where the generators satisfy the relations if |i–j|=1 and e_ie_j=e_je_i if |i–j|2. We use the Four Color Theorem to give a necessary and sufficient condition for certain elements of T_n to be nonzero. It turns out that the characterization is, in fact, equivalent to the Four Color Theorem.* Partially supported by NSF under Grant DMS-9802859 and by NSA under grant MDA904-97-1-0015. Partially supported by NSF under Grant DMS-9623031 and by NSA under Grant MDA904-98-1-0517.     

Controllability of a quantum particle in a moving potential well

We consider a nonrelativistic charged particle in a 1D moving potential well. This quantum system is subject to a control, which is the acceleration of the well. It is represented by a wave function solution of a Schrödinger equation, the position of the well together with its velocity. We prove the following controllability result for this bilinear control system: given ψ₀ close enough to an eigenstate and ψ_f close enough to another eigenstate, the wave function can be moved exactly from ψ₀ to ψ_f in finite time. Moreover, we can control the position and the velocity of the well. Our proof uses moment theory, a Nash-Moser implicit function theorem, the return method and expansion to the second order.     

Space tilings and substitutions

We generalize the study of symbolic dynamical systems of finite type and ² action, and the associated use of symbolic substitution dynamical systems, to dynamical systems with ² action. The new systems are associated with tilings of the plane. We generalize the classical technique of the matrix of a substitution to include the geometrical information needed to study tilings, and we utilize rotation invariance to eliminate discrete spectrum. As an example we prove that the pinwheel tilings have no discrete spectrum.Research supported in part by NSF Grant No. DMS-9304269 and Texas ARP Grant 003658-113     

The dimension of interior levels of the Boolean lattice

LetP(k,r;n) denote the containment order generated by thek-element andr-element subsets of ann-element set, and letd(k,r;n) be its dimension. Previous research in this area has focused on the casek=1.P(1,n–1;n) is the standard example of ann-dimensional poset, and Dushnik determined the value ofd(1,r;n) exactly, whenr2 . Spencer used the Erdös-Szekeres theorem to show thatd(1, 2;n) lg lgn, and he used the concept of scrambling families of sets to show thatd(1,r;n)=(lg lgn) for fixedr. Füredi, Hajnal, Rödl and Trotter proved thatd(1, 2;n)=lg lgn+(1/2+o(1))lg lg lgn. In this paper, we concentrate on the casek2. We show thatP(2,n–2;n) is (n–1)-irreducible, and we investigated(2,r;n) whenr2 , obtaining the exact value for almost allr.The research was supported in part by NSF grant DMS 9201467.The research was supported in part by the Universities in Russia program.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

Branchings in rooted graphs and the diameter of greedoids

LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr ²–r+1 (r>0). This answers a question by L. Lovász.There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr.Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2^r–1.