International Journal of Control, Vol.89, No.2, 352-367, 2016
Solution of the determinantal assignment problem using the Grassmann matrices
The paper provides a direct solution to the determinantal assignment problem (DAP) which unifies all frequency assignment problems of the linear control theory. The current approach is based on the solvability of the exterior equation v(1) boolean AND v(2) boolean AND ... boolean AND v(m) = z, where z is an element of boolean AND(m) U, v(i) is an element of U, U is an n-dimensional vector space over F which is an integral part of the solution of DAP. New criteria for existence of solution and their computation based on the properties of structured matrices are referred to as Grassmannmatrices. The solvability of this exterior equation is referred to as decomposability of z, and it is in turn characterised by the set of quadratic Plucker relations (QPRs) describing the Grassmann variety of the corresponding projective space. Alternative new tests for decomposability of the multi-vector z are given in terms of the rank properties of the Grassmannmatrix, Phi(m)(n) (z) of the vector z, which is constructed by the coordinates of z is an element of boolean AND U-m. It is shown that the exterior equation is solvable (z is decomposable), if and only if dim N-n(m) (z) = m, where N-n(m) (z) = Nr {Phi(n)(n)(z)}; the solution space for a decomposable z, is the space N-n(m) (z) = V-z = sp{v(i), i is an element of m}. This provides an alternative linear algebra characterisation of the decomposability problem and of the Grassmann variety to that defined by the QPRs. Further properties of the Grassmann matrices are explored by defining the Hodge-Grassmann matrix as the dual of the Grassmann matrix. The connections of the Hodge-Grassmannmatrix to the solution of exterior equations are examined, and an alternative new characterisation of decomposability is given in terms of the dimension of its image space. The framework based on the Grassmann matrices provides the means for the development of a new computational method for the solutions of the exact DAP (when such solutions exist), as well as computing approximate solutions, when exact solutions do not exist.