Vandermonde independent matrices, basic sets, and polynomial matrix functions over a finite field

Let D and R be sets and let denote a collection of functions from D to R. A subset S of D is called a basic set for iff every function g:S→R has a unique extension . For a given class such a set may or may not exist. After discussing several related concepts and deriving a few of the elementary properties of basic sets in general, this paper examines the question of whether or not basic sets exist for a particular class of matrix functions over a finite field. Specifically, if Fq denotes the finite field of q elements and denotes the algebra of n × n matrices of Fq , then a function is called a right polynomial function on iff there arc matrices A0 ,…,Am in such that for all . The collection of all right polynomial functions on , denoted by , is the class of interest in this paper. The question of whether or not basic sets exist for leads in a natural way to the introduction of the following concept of independence for a set of matrices. A subset {X 1,…,Xt} of is called a V-independent set iff the generalized Vandermonde matrix is invertible. The collection of all Kindependent subsets of is a partially ordered set (under set inclusion) and is the combinatorial structure of interest here. It is shown that a basic set exists for iff the cardinality of a maximum V-independent set is arbitrary, it is proved by construction that a basic set exists and consequently that a maximum V-independent set has q2 +q elements. Some discussion is given for the general case, and in particular it is shown that within the poset of V-independent sets, a maximal set is not necessarily a maximum set.