The algebraic matroid of the funtf variety
Daniel Irving Bernstein Cameron Farnsworth Jose Israel Rodriguez


A finite unit norm tight frame is a collection of r vectors in 
ℝ^n that generalizes the notion of orthonormal bases. 
The affine finite unit norm tight frame variety is the Zariski closure of the set of finite unit norm tight frames.
Determining the fiber of a projection of this variety onto a set of coordinates is called the algebraic finite unit norm tight frame completion problem.

Our techniques involve the algebraic matroid of an algebraic variety, which encodes the dimensions of fibers of coordinate projections.
This work characterizes the bases of the algebraic matroid underlying the variety of  finite unit norm tight frames in ^3.
Partial results towards similar characterizations for finite unit norm tight frames in 
 ^n with n ≥ 4 are also given. We provide a method to bound the degree of the projections based off of combinatorial data.








[2010]05B35




Institute for Data, Systems, and Society, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139
dibernst@mit.eduhttps://dibernstein.github.io


Department of Mathematics,         Texas State University,  601 University Drive, San Marcos, TX 78666-4684, USA.
[Corresponding author]clf129@txstate.edu


Department of Mathematics,         University of Wisconsin-Madison,  480 Lincoln Drive, Madison WI 53706-1388, USA.
jose@math.wisc.eduhttp://www.math.wisc.edu/ jose/


The algebraic matroid of the finite unit norm tight frame (funtf) variety
    Jose Israel Rodriguez
    Received: date / Accepted: date
=========================================================================











§ INTRODUCTION


A set of unit vectors {w_1,…,w_r}  in 
ℝ^n is said to be a finite unit norm tight frame (or funtf) if 
the matrix 
W:=[[ w_1 w_2   … w_r ]]
satisfies n/r WW^T = _n, where _n is the n× n identity matrix.
This generalizes the notion of orthonormal bases for ℝ^n.
The Zariski closure (over ) of the set of n× r matrices that are finite unit norm tight frames forms an algebraic variety in ^n× r,
which we  denote by . The variety  can be expressed as an algebraic set
(see <cit.> and <cit.>) as follows:
  
    =
    	{∈^n× r    :
    	^T=r /n _n, 
    	 (^T)=(_r)
    	},

where (M) denotes the diagonal entries of a matrix M.

In this paper, we characterize the algebraic matroid underlying X_3,r  and provide additional partial results for X_n,r.


The remainder of this section describes the applied motivation for our work here and gives a literature review of the area. 

In Section <ref>, we provide the minimum necessary background on algebraic matroids.
In Section <ref> we set up our notation and collect previous results we will need about .
In particular, we discuss how matroids arise in connection with algebraic frame completion problems.
In Section <ref>, we provide our main results on the algebraic matroid underlying   (Theorem <ref>).

Section <ref> gives a recursive formula for computing the degree of a finite-to-one coordinate projection of  (Theorem <ref>)
which we then use to completely characterize the degrees of projection onto a basis of X_3,r.





 §.§ Algebraic frame theory

Frames  generalize the notion of a basis of a vector space and have found use in numerous fields of science and engineering.


Given a Hilbert space , a frame is a set of elements {f_k}_k∈ I⊂
such that there exist real numbers A,B such that  0<A≤ B<∞ and for every h∈


    Ah^2≤∑_k∈ I|⟨ h,f_k⟩|^2≤ Bh^2.


These frame conditions are given by Duffin and Schaeffer in <cit.>. If A=B, then the frame is called tight.

If  is n-dimensional, then any frame has at least n elements.
A frame where each element has norm one is said to be a unit norm frame. 


In the literature unit norm frames are also known as normalized frames, uniform frames, and spherical frames. Throughout this text, we identify the sequence of vectors in a frame with the matrix whose columns are the vectors in the frame. The frames we are interested in are frames of the Hilbert space ℝ^n; however, it is important to keep in mind that we are making a relaxation to a question regarding an algebraic variety in ℂ^n× r.


A finite frame which is both tight and unit norm is also called a finite unit norm tight frame and is commonly abbreviated in the literature as funtf.
Such frames are the focus of much research because they minimize various measures of error in signal reconstruction <cit.>.
Algebraic frame theory uses the powerful tools of computational algebraic geometry to solve problems involving finite frame varieties. Such approaches have found success in <cit.>.


 


Given an n× r matrix where only a subset of the entries are observed,
the finite unit norm tight frame completion problem asks for values of the missing entries such that the resulting completed matrix is a funtf.
The jumping off point for this work is the relaxation of this problem that allows for the missing entries to take on complex values.
We call this relaxation the algebraic finite unit norm tight frame completion problem.


Complex frames are also studied where a Hermitian inner product is used, but that is not the focus of this article.

Studying the variety  in place of the set of finite unit norm tight frames gives one access to tools from algebraic geometry,
and results about  can lead to insight about the set of finite unit norm tight frames—see for example <cit.>.
Many works have studied the properties of various sets of frames considered as varieties.
For example, dimensions of (μ,S)-frame varieties, which are spaces of matrices W=[w_1⋯ w_r], real or complex, satisfying WW^*=S
for some Hermitian (symmetric) positive definite matrix S such that w_k=μ_k, were considered in <cit.>. Finite unit norm tight frames are a special case of these (μ,S)-frames where μ_i=1 and S is a scalar multiple of the identity matrix. Along with the fundamental groups, the dimensions of finite unit norm tight frame varieties were derived in <cit.>. 

 In <cit.>, nonsingular points of (μ,S)-frames are characterized along with the tangent spaces at these nonsingular points on these varieties. The connectivity of the finite unit norm tight frame variety along with its irreducibility are studied in <cit.>. In <cit.>, the polytope of eigensteps of finite equal norm tight frames is studied.
 
 These eigensteps are sequences of interlacing spectra used by <cit.> to construct finite frames of prescribed norms

and the dimension of finite unit norm tight frame varieties is noted to be related to the dimension of these polytopes.






 §.§ Algebraic finite unit norm tight frame completion

Due to their robustness to erasures and additive noise, unit norm tight frames play an important role in signal processing.
Explicit constructions for unit norm tight frames are quite recent despite theoretical work regarding existence being quite classical.
The Schur-Horn Theorem <cit.> characterizes the pairs (λ,μ) such that there exists
a frame whose frame operator has spectrum λ and lengths μ.



 There exists a positive definite self-adjoint matrix with spectrum {λ_i}_i=1^r and diagonal entries {ν_i}_i=1^r if and only if {λ_i}_i=1^r≽{ν_i}_i=1^r.


Where {λ_i}_i=1^r≽{ν_i}_i=1^r means {λ_i}_i=1^r and {ν_i}_i=1^r are nonnegative, nonincreasing sequences which sum to the same value, and the partial sums of {λ_i}_i=1^r are greater than or equal to the partial sums of {ν_i}_i=1^r:


    ∑_l=1^iλ_l≥∑_l=1^iν_l,  ∀ i=1,…,r-1


If {λ_i}_i=1^r and {ν_i}_i=1^r meet the preceding properties it is said that {λ_i}_i=1^r majorizes {ν_i}_i=1^r.

However, explicit constructions for these frames have remained scarce.
In <cit.> the authors give a constructive characterization for all unit norm tight frames in ^2
and provide a construction technique known as harmonic frames for unit norm tight frames in ^n.
An alternative constructive technique called spectral tetris is given in <cit.>.
An explicit construction of every unit norm tight frame was finally given by <cit.>.



The previous paragraph covers results on explicitly constructing frames with prescribed spectrum and whose vectors' lengths are prescribed.
However, what if you have specific vectors you want included in your frame? How do you complete this partial set of vectors into a tight frame?
The work
 <cit.> answers how many vectors must be added to complete your set of vectors into a tight frame, and in the case when all vectors are unit norm, they also provide a lower bound (which is not sharp) for the number of vectors required to complete the set of vectors into a tight frame.  The minimum number of vectors needed to add to your set of vectors to complete it to a frame when their norms are prescribed is provided by <cit.>. In both papers, it is assumed that you start with a set of vectors. See also <cit.>, in which the authors characterize the spectra of all frame operators of frames completed from the addition of extra vectors to another frame and discuss completion in such a way as to produce a frame minimizing the condition number, the mean squared reconstruction error, and the frame potential. 

In this paper, we take a different approach than Feng, Wang, and Wang, Massey and Ruiz, or Fickus, Marks, and Poteet. Instead of starting with a set of vectors and asking how many more vectors are needed to have a tight frame,  we have the following generalization of the problem.


Given a partially observed n× r matrix,
determine if the missing entries can be completed such that the columns form a finite unit norm tight frame.



A generalization of Problem <ref> is to ask how many completions there are. 


Given some known entries of an  n× r matrix, 
find the cardinality of the number of completions 
such that the columns form a finite unit norm tight frame.


When studying the algebraic geometry of low-rank matrix completion,
one often studies the analogue of Problems <ref> and <ref>,
where instead of completing to a finite unit norm tight frame,
one completes to a matrix of a particular specified low rank <cit.>.

Problem <ref> can be studied using algebraic geometry 
by considering the known entries as a set of defining equations of an affine linear space ℒ in ℂ^n× r and then studying the degree of 
∩ℒ.
When  ∩ℒ is finite a set of points,
the degree of ∩ℒ is the number of points, counted with multiplicity,
and is an upper bound for the number of completions.  
The degree of ∩ℒ need not coincide with the degree of ,
but when the linear space ℒ is generic such that ∩ℒ≠∅, 
the degree of ∩ℒ and  are the same. 
For n=r, the variety  is the orthogonal group and the degree of this variety was determined 
in <cit.> using representation theory.
An analogous question from rigidity theory
asks for the number of realizations of a rigid graph.
This same algebraic approach for getting an upper bound works in this context,
this time by computing or bounding the degree of (coordinate projections of) the Cayley-Menger variety <cit.>.

After solving Problem <ref>,
the most natural next problem is to actually compute such a completion, if it exists.
One can attempt to do this using Gröbner bases algorithms, but this is likely to be prohibitively slow.
A faster way to do this would be using numerical algebraic geometry
using e.g.  <cit.>,  <cit.>, or  <cit.>.
Knowing the degree of coordinate projections of  could be helpful in this approach.
One could could also try using the combinatorics of the set of known entries
to derive polynomials in the missing entries that could be solved to complete
the finite unit norm tight frame.
In the language of algebraic matroids,
this is the problem of finding combinatorial descriptions of the circuit polynomials of .
This would be an interesting future direction.








§ THE BASICS OF ALGEBRAIC MATROIDS

We now take a detour to introduce the minimum necessary background on algebraic matroids.
Since the only matroids considered in this paper will be algebraic,
we will not discuss or define abstract matroids.
Moreover, our study will be limited to those that are algebraic over  or .
The reader who is interested in learning about more general (algebraic) matroids is advised to consult the textbook <cit.>.

Let  be a field.
Given a finite set E,
we let ^E denote the vector space whose coordinates are indexed by the elements of E.
Each subset S ⊆ E of coordinates is associated with the linear projection π_S: ^E →^S
that sends each point (x_e)_e ∈ E to (x_e)_e ∈ S.
The ring of polynomials with coefficients in  and indeterminants indexed by E will be denoted [x_e: e ∈ E]
and the corresponding field of rational functions will be denoted (x_e: e ∈ E).
The ideal in [x_e: e ∈ E] generated by a finite set of polynomials f_1,…,f_k ∈[x_e : e ∈ E]
will be notated as (f_1,…,f_k).
Given a set X ⊆^E, we let I(X) denote the ideal of all polynomial functions that vanish on X.

	Let E be a finite set, let  be  or , and let X ⊆^E be an irreducible variety.
    A subset of coordinates S ⊆ E is
    
        
  * independent in X if I(π_S(X)) is the zero ideal
        
  * spanning in X if (π_S(X)) = (X)
        
  *  a basis of X if S is both independent and spanning.
    
    Any one of the three set systems consisting of the independent sets,
    the spanning sets, or the bases of an irreducible variety determines the other two.
    The combinatorial structure specified by any one of these set systems is called the algebraic matroid underlying X.



    Let X ⊂^[4] be the linear variety defined by the vanishing of the linear forms x_1 - 5x_2 = 0 and x_3+2x_4 = 0.
    The bases of X are
    
    {1,3},   {1,4},   {2,3},   {2,4}.

    The independent sets of X are the subsets of the bases,
    and the spanning sets are the supersets.
    Moreover, all the bases have cardinality two, which is also the dimension of X.
    This is not a coincidence—see Proposition <ref> below.


We now describe the intuition behind the algebraic matroid underlying an irreducible variety X ⊆^E.
When S ⊆ E is independent,
the coordinates (x_e)_e ∈ S can be given arbitrary generic values, and the resulting vector can be completed
to a point in X.
When S ⊆ E is spanning and x ∈ X is generic,
then the coordinates (x_e)_e∉ S can be determined by solving a zero-dimensional system of polynomials
whose coefficients are polynomials in (x_e)_e ∈ S.
In other words, the set π_S^-1(π_S(x)) ∩ X is generically finite.

It's important to recall Definition <ref> requires  X to be an irreducible variety.
This ensures that the algebraic matroid underlying X is indeed a matroid (see for example <cit.>).
Proposition <ref> below then follows from the fact that all bases of a matroid have the same size <cit.>.



For any basis B⊆ E of an irreducible variety X⊆𝕂^E, the cardinality of the set B equals (X).




Given finite sets A and B and a field , we let ^A× B denote the set of matrices with entries in 
whose rows are indexed by elements of A and whose columns are indexed by elements of B.
Given polynomials f_1,…,f_k∈[x_e: e ∈ E]
the Jacobian matrix of f_1,…,f_k is the matrix J(f_1,…,f_k) ∈ ((x_e: e ∈ E))^[k]× E
whose (i,e) entry is the partial derivative ∂ f_i/∂ x_e.
In Section <ref>, we will often work with submatrices of a Jacobian matrix.
For this reason, we introduce the following notation.

Let M denote a matrix whose columns are indexed by a set E.
The submatrix of a given M with columns corresponding to the elements of a subset S of E
is denoted M_S.



The following proposition is useful for computing the bases of the algebraic matroid underlying a given irreducible variety.
It is well known, and usually stated in terms of matroid duals.
We state it here in more elementary terms for the purposes of keeping the necessary matroid theory background at a minimum.
For more details, see <cit.> and <cit.>.


    Let E be a finite set, let  be  or  and let X ⊆^E be an irreducible variety of dimension d
    such that I(X) = (f_1,…,f_k).
    A subset S ⊆ E of size d is a basis of X if and only if the rank of J(f_1,…,f_k)_E∖ S is |E|-d.





§ ALGEBRAIC MATROIDS TO ALGEBRAIC FUNTF COMPLETION





Recall from Section <ref> that the Zariski closure in ^× of the
set of
× matrices  such that the columns form a finite unit norm tight frame is
denoted by . In other words,
this paper studies the following algebraic relaxation of Problem <ref>.
[The algebraic frame completion problem]
	Given some known entries of an n× r matrix,
	determine if the matrix can be completed to an element of .


We say  is an affine finite unit norm tight frame variety and call a matrix in  a finite unit norm tight frame (funtf) matrix.
The  n+12 + r  scalar equations defining  shown in (<ref>)
were found in <cit.> and <cit.>. 
We will express the polynomials defining the affine finite unit norm tight frame variety in the ring [x_ij: 1≤ i ≤ n, 1 ≤ j ≤ r] where x_ij will represent the ij entry of a matrix.


Indeed, the column norm constraints on W can be expressed as the following  polynomials set to zero:

    (_1,…,_) :=(^T-_),


while the orthogonal row constraints on W can be expressed as the following n+12 polynomials f_ij, i≤ j:

    [ f_11 f_12    … f_1n; f_12 f_22    … f_2n;    ⋮         ⋱    ⋮; f_1n f_2n    … f_nn ] : =WW^T-/_.








    Elementary algebra shows that these polynomials satisfy the following relation
    	
    ∑_i=1^n f_i,i = ∑_j=1^r g_j = ||W||_F^2-r,

	where ||· ||_F denotes the Frobenius norm.


The problem of algebraic finite unit norm tight frame completion can be cast as the problem of projecting an affine finite unit norm tight frame variety to a subset of coordinates.
Let E ⊆ [n]× [r] denote a subset of coordinates of ^×.
We will think of E as indexing “known” entries,
and the algebraic finite unit norm tight frame completion problem is to determine the remaining “unknown” entries
so that the completed matrix is a finite unit norm tight frame.
Let π_E
denote the respective coordinate projection.
The algebraic finite unit norm tight frame completions of a given M ∈^E are the elements of the fiber π^-1_E(M).
It follows that E is independent in  if and only if every generic M ∈^E has an algebraic finite unit norm tight frame completion
and that E is spanning in  if and only if each nonempty fiber π^-1(π_E(M)) is finite when M is generic.
Thus in the generic case, Problem <ref> is equivalent to the following.


    Find a combinatorial description of the algebraic matroid underlying 


The first steps towards solving Problem <ref> are determining the irreducibility and dimension of .
Fortunately, this was done in <cit.>, <cit.>, and <cit.> which we summarize in the following theorem.


    The dimension of the affine finite unit norm tight frame variety  is
    
    () = nr-n+12 - r + 1     provided r>n≥ 2.

    It is irreducible when r ≥ n+2 > 4.


In our work, we look to determine each basis (Definition <ref>, item <ref>) of .
We restrict our study to r ≥ n+2 > 4 so that  is irreducible and thus gives a matroid.
We seek a combinatorial description using bipartite graphs.
Bipartite graphs provide a natural language for attacking Problem <ref>.
Given finite sets A and B and a subset S ⊆ A × B, we let (A,B,S) denote the bipartite
graph with partite vertex sets A and B and edge set S.
We call two bipartite graphs (A_1,B_1,S_1) and (A_2,B_2,S_2) bipartite isomorphic if there exists
a graph isomorphism ϕ: A_1 ∪ B_1 → A_2 ∪ B_2 such that ϕ(A_1) = A_2 and ϕ(B_1) = B_2.

Every subset E of entries of an n× r matrix can be identified with the bipartite graph ([n],[r],[n]× [r] ∖ E),
which we denote by G_E.
The edges of G_E are in bijection with the complement of E and not E itself.
This stands in contrast to what is often done in the algebraic matrix completion literature,
but will make our results much cleaner to state.
Neither row-swapping nor column-swapping affects whether a given subset E of entries of an n× r matrix
is an independent set (or a basis, or spanning set) of .
Therefore, whether a given subset E of entries is independent (or a basis or spanning) in  only depends
on the bipartite isomorphism equivalence class of G_E.
The (non-bipartite) graph isomorphism class of G_E may not be sufficient to determine
whether E is independent (or a basis or spanning) in  because the transpose of a finite unit norm tight frame matrix  may not be funtf.
So from now on, we will only consider bipartite graphs up to their bipartite isomorphism classes.
We may now phrase Problem <ref> more concretely as follows.




    For which (bipartite isomorphism classes of) bipartite graphs G_E is E a basis of ?


We will sometimes find it useful to represent a subset E ⊆ [n]× [r]
as the {0,1}-matrix whose ij entry is 1 if (i,j) ∈ E and 0 otherwise.
Such a representation will be called a matrix entry representation.








§ THE ALGEBRAIC MATROID UNDERLYING THE FINITE UNIT NORM TIGHT FRAME VARIETY

In this section we give combinatorial criteria on the bases of .
First we show that if E is a basis of , then the graph G_E is connected.

Moreover, when n=3 the converse is true as well.
Second,
we show that whether or not E is a basis of  only depends on the  2-core of G_E.
This allows us to determine a combinatorial criterion for every  after fixing .




 §.§ Graph connectivity

We begin with some graph theoretic definitions.
Let G = (A,B,S) be a bipartite graph.
The greater 2-core of G, denoted _2(G), is the graph obtained from G by iteratively removing all edges that are incident to a vertex of degree one.
The 2-core of G, denoted _2(G), is the graph obtained by deleting the isolated vertices from _2(G).
Figure <ref> shows a graph alongside its greater 2-core and its 2-core.




Since the graph G need not be connected, there may not exist a spanning tree for G. Instead,  consider a spanning forest for G, which is a maximal acyclic subgraph of G, or equivalently a subgraph consisting of a spanning tree in each connected component.   

A circuit is a nonempty trail in G such that the first and last vertex coincide, or equivalently, a non-empty sequence (e_1,…,e_k) of edges in G
for which there is a sequence of vertices (v_1,…,v_k,v_1)
such that for  i=1,…,k-1 the vertices of e_i are (v_i,v_i+1)
and the vertices of e_k are (v_k,v_1). 
A cycle is an example of a circuit. 

Given a spanning forest F of G
and an edge e of G not appearing in F,
the graph F ∪{e} has exactly one cycle which must contain e.
This cycle is called the fundamental circuit of e with respect to F.
    

Given a subset S'⊆ S of the edge set of G, the characteristic vector of S'
is the vector in {0,1}^S  that has ones at entries corresponding to elements of S'
and zeros at all other entries.
The incidence matrix of G is the matrix whose rows are indexed by the vertices of G,
and the row corresponding to a vertex v is the characteristic vector of the set of edges that are incident to v.
The columns of the incidence matrix of G are indexed by the edges of G.



We use the notation K_a,b to denote the complete bipartite graph on partite sets of size a and b.
The incidence matrix of K_3,5 is given by the 8× 15 matrix below

    ([ 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1; 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0; 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0; 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0; 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0; 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ]).

This matrix is naturally partitioned via the vertices in each partite of the graph K_3,5.



    Assume r ≥ n+2 > 4
    and let E ⊆ [n]× [r] have cardinality nr - n+12 - r + 1.
    If E is a basis of ,
    then G_E is connected.
    When n=3, the converse is true as well.


Let g_i and f_ij denote the polynomials as in (<ref>) and (<ref>); this set of polynomials generate the ideal of .
	Let J be the (r+n+12) × nr Jacobian matrix
    
    J:=J(g_1,…,g_r,f_11,f_12…,f_nn).

	Proposition <ref> implies that
    E is a basis of  if and only if
    the (r+n+12)× (r+n+12-1)
    matrix J_[n]×[r]∖ E has full rank,  
     or equivalently, 
     
    (J_[n]×[r]∖ E)=r +n+12 - 1.


    Let J' and J” denote the following matrices of size (r+n+12)× nr and (r+n)× nr, respectively
	
    J'   :=J ·(1/x_11,1/x_12…,1/x_nr),
    
    	    J”   :=J(g_1,…,g_r,f_11,f_22,…,f_ii,…,f_nn)·(1/x_11,1/x_12…,1/x_nr),

    where (w) denotes the matrix with the vector w along its diagonal.


The matrix J” is twice the incidence matrix of K_n,r from Example <ref>,
 and J”_[n]× [r]∖ E
    is twice the incidence matrix of G_E.
    Thus if G_E has c connected components, then
    
    (J”_[n]× [r]∖ E)= r+n-c.

    On the other hand, since J' can be obtained from J” by including n2 additional rows, we have
    
    (J'_[n]× [r]∖ E) ≤ (J”_[n]× [r]∖ E)+n2
    	 =    r + n+12-c.


Since (J_[n]× [r]∖ E) = (J'_[n]× [r]∖ E),
we have that if G_E is disconnected, then J_[n]× [r]∖ E is rank deficient and thus E is not a basis.

	Now, having proved that E being a basis implies connectivity of G_E,
    we assume that n = 3 and prove the converse.
    Further assume that G_E is connected with n+12+r-1=r+2 edges.
    We will show that E is a basis of  by showing that J'_[n]×[r]∖ E has full rank.
    	This is done by splitting J'_[n]×[r]∖ E into two row submatrices whose kernels intersect trivially.

    Twice the incidence matrix of the complete bipartite graph K_3,r is a row-submatrix of J'.
    Therefore, any linear relation among the columns of J' must lie in the linear space
    
    {v_C: C  is a circuit of  K_3,r}

    where v_C ∈^[3]× [r] is the {1,-1,0}-vector obtained from the characteristic vector of C
    by
    giving adjacent edges opposite signs.

    The row of J' corresponding to the constraint f_ab=0 with a ≠ b
    has x_bi/x_ai at the column corresponding to x_ai and x_ai/x_bi at the column corresponding to x_bi.
    For ease of notation, we introduce the change of variables
    
    t_1i := x_2i/x_1i     t_2i := x_3i/x_1i.

    With this change of variables, the rows of J' corresponding to the constraints f_12=f_13=f_23=0
    form the matrix K shown below
    
    K:=   x_11   …    x_1r    x_21   …    x_2r    x_31   …    x_3r
                f_12   t_11   …    t_1r    t^-1_11   …    t^-1_1r    0    …    0 
                f_13   t_21   …    t_2r    0    …    0     t^-1_21   …    t^-1_2r
                f_23   0    …    0     t_21t^-1_11   …    t_2rt^-1_1r    t_11t^-1_21   …    t_1rt^-1_2r.

    Fix a spanning tree T of G_E and let e_1,e_2,e_3 denote the three edges of G_E that are not contained in T.
    Let C_i denote the fundamental circuit of e_i with respect to T.
    The space of linear relations among the columns of J' corresponding to the edges of G_E
    lies within the three-dimensional subspace {v_C_i: i = 1,2,3}.
    We now show that no nonzero element of {v_C_i: i = 1,2,3} lies in the kernel of K.
    It will then follow that the column-submatrix of J' corresponding to the edges of G_E has maximum rank.

    The three fundamental circuits C_1,C_2, and C_3 all lie in _2(G_E)
    which is a bipartite graph on partite sets of size n'≤ 3 and r' ≤ r.
    Each vertex of _2(G_E) has degree at least 2, so n',r'≥ 2.
    Since G_E is connected, _2(G_E) must also be connected.
    Hence since C_1,C_2, and C_3 all lie in _2(G_E),
    _2(G_E) must have exactly n'+r'+2 edges.
    Since each vertex has degree at least 2, 2r' ≤ n'+r'+2 and so r' ≤ n'+2.
    So thus far, we only need to consider
    (n',r') = (2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(3,5).
    Among these, the only (n',r')-pairs such that there even exists such a bipartite graph with the correct number of edges
    are (2,4),(3,3),(3,4),(3,5).
    For these values of (n',r'),
    we may compute all the connected bipartite graphs on partite sets of size n' and r'
    with minimum degree 2 and exactly n'+r'+2 edges using the  command of  <cit.>.
    There are seven such graphs and they are displayed in Figure <ref>
    with vertices labeled according to which row or column they correspond to.
    
    
    
    
    
    
    
    
    
    

    By relabeling vertices, we may assume that _2(G_E) is supported on partite vertex sets 1,…,n' and 1,…,r'.
    Let A__2(G_E) denote the incidence matrix of _2(G_E)
    and let M__2(G_E) denote the matrix whose columns are a basis of the kernel of A__2(G_E).
    Then {v_C_i: i = 1,2,3} is the span of M__2(G_E).
    Letting K' be the submatrix of K with columns corresponding to the edge set of _2(G_E),
    we are done if we show that K'M__2(G_E) has rank 3 for the seven values of _2(G_E) above.
    This is verified in a Mathematica script available at the following url<cit.>.

<https://dibernstein.github.io/Supplementary_materials/funtf.html>

This Mathematica script computes each of the symbolic matrices K'M__2(G_E),
then calculates their rank as matrices with entries in the appropriate function field.


The following proposition is useful to construct examples showing that the converse of Theorem <ref> is not true for n ≥ 4.


	Assume r ≥ n+2 > 4 and
	let E ⊆ [n]× [r]. 
    If E is spanning in ,
    then at most two vertices of G_E corresponding to columns can have degree n.


    Assume G_E has k column vertices of degree n.
    Without loss of generality, assume they correspond to the first k columns
    so that (a,i) ∉ E for all 1 ≤ a ≤ n, 1 ≤ i ≤ k.
    Define E' := {(a,i): 1 ≤ a ≤ n, k+1 ≤ i ≤ r}, and observe
    E ⊆ E'.
    We show that when k ≥ 3, the dimension of π_E'^-1(π_E'(M)) is positive for generic M.
    It follows that E', and therefore E, is not spanning.

   
    
    Let M ∈ be a generic finite unit norm tight frame.
    The (i,a) entry of M will be denoted m_ia.
    Let g̃_a, f̃_ij denote the polynomials obtained from g_a 
    and f_ij,
    as in (<ref>) and (<ref>),
    by plugging in m_ia for x_ia when (i,a) ∈ E'.
    The Zariski closure of π_E'^-1(π_E'(M)) can be identified with the variety in ^n× k
    defined by the polynomials g̃_1,…,g̃_k and f̃_ij for 1 ≤ i ≤ j ≤ n.
    
    Following from Equation <ref>, we have 
    
    f̃_11 + f̃_22 + … + f̃_nn = g̃_1 + … + g̃_k

    
    and so π_E'^-1(π_E'(M)) is in fact the vanishing locus of g̃_1,…,g̃_k-1 and f̃_ij for 1 ≤ i,j ≤ n.
    Moreover, the polynomials
    
    f̃_ij + δ_ijr/n - ∑_a = k+1^r m_iam_ja     where    δ_ij :=
        	
        	    1     i = j
    
        	    0     i ≠ j

    parameterize the variety of n× n symmetric matrices of rank at most k,
    which has dimension nk-k2 (see for example <cit.>).
    Thus the n+12 polynomials f̃_ij, 1 ≤ i≤ j ≤ n
    together contribute at most nk-k2 to the codimension of π_E'^-1(π_E'(M)).
    Hence the codimension of π_E'^-1(π_E'(M)) is at most nk-k2 + k-1,
    which is strictly less than nk for k ≥ 3.



    Let n ≥ 4 and r ≥ n+2 and let E' := {(i,a): 2 ≤ i ≤ n, 4 ≤ a ≤ r}.
    Let E be obtained from E' by removing any n-22-1 elements.
    Then E has nr - n+12 - r + 1 elements and G_E is connected.
    However, Proposition <ref> implies that E cannot be a basis of .
    Figure <ref> shows examples of this construction for n = 4 and n = 5.

    




 §.§ Combinatorial criteria with fixed row size

The goal of this section is to fix  and find a combinatorial criteria to determine if E is a basis of  for any .
This is made precise in Remark <ref>.

The following theorem tells us that whether or not a given E ⊆ [n]× [r] of cardinality nr-n+12-r+1
is a basis in  depends only on _2(G_E).


	Assume r ≥ n+2 > 4 and let E ⊆ [n]× [r] such that |E| = nr-n+12 - r + 1.
    Then E is a basis in the algebraic matroid underlying  if and only if
    the set E' ⊇ E satisfying G_E' = _2(G_E) is spanning in .
    Moreover, for a fixed n, there are only finitely many possible graphs appearing as _2(G_E)
    as E ranges over all bases of .



	Let M ∈ be a generic finite unit norm tight frame whose (i,a) entry is m_ia.
	Let g̃_a and f̃_ij denote the polynomials obtained from g_a and f_ij
	by setting x_ia = m_ia when (i,a) ∈ E.
	Then π_E^-1(π_E(M)) can be viewed as the zero-dimensional variety in ^[n]×[r]∖ E defined
	by the vanishing of the polynomials g̃_a, 1 ≤ a ≤ r and f̃_ij, 1 ≤ i ≤ j ≤ n.
	Since G_E is connected, the edges of G_E that are not in _2(G_E) can be ordered (i_1,a_1),…,(i_k,a_k)
	such that for each j,
	in either g̃_a_j or f̃_i_j i_j,
	every variable other than x_i_j a_j that appears is of the form x_i_l a_l for some l < j.
	It follows that given π_E(M),
	one can solve a series of quadratic equations in order to recover, up to finite ambiguity,
	the entries of M at positions corresponding to edges of G_E that are not in _2(G_E).
	One can then solve for the remaining entries of M precisely when _2(G_E) is spanning in .
    The “moreover” clause follows by Proposition <ref> below.



Given a set E ⊆ [n]× [r] that is spanning in ,
the set E ∪{(1,r+1),…,(n,r+1)} is spanning in X_n,r+1.
Thus Theorem <ref> tells us that if we fix n but allow r to vary,
then the problem of determining whether or not E ⊂ [n]× [r] is a basis of 
is equivalent to determining whether or not _2(G_E) appears on a certain finite list.
Proposition <ref> below gives us the finiteness statement in Theorem <ref>,
as well as bounds on the size of _2(G).



	Let r ≥ n+2 > 4 and let E ⊆ [n]× [r] such that G_E is connected.

    Let α and β be the number of row- and column-vertices (respectively) in _2(G_E).
    If E is a basis of , then
    
        
  * α = n-1 or α = n
        
  * α≤β≤n2 + α - 1.
    


	Let M ∈ be a generic finite unit norm tight frame
	 whose (i,a) entry is m_ia.
	Let g̃_a and f̃_ij denote the polynomials obtained from g_a and f_ij
	by setting x_ia = m_ia when (i,a) ∈ E.
	Then π_E^-1(π_E(M)) can be viewed as the zero-dimensional variety in ^[n]×[r]∖ E defined
	by the vanishing of the polynomials g̃_a, 1 ≤ a ≤ r and f̃_ij, 1 ≤ i ≤ j ≤ n.

	First we show α=n-1 or α=n.
    Without loss of generality,
    assume that _2(G_E) has row-vertices 1,…,α and column vertices 1,…,β.
    Let F := {(i,a): 1 ≤ i ≤α, 1 ≤ a ≤β}∖ E be the edge set of _2(G_E). 
    This set has cardinality given by  |F| = α + β + n2 - 1.
    The elements of F index the entries in the upper-left submatrix of M that are,
    in principle,
    allowed to vary over the fiber π_E^-1(π_E(M)).
    After dropping one of the redundant g̃_a's via (<ref>),
    there are exactly α + 12 + β - 1 + α(n-α)
    equations among the g̃_a's and f̃_ij's that involve entries in the upper-left α×β block of M.
    Since π_E^-1(π_E(M)) is zero-dimensional,
    we must have
    
    α + β + n2 - 1 ≤α + 12 + β - 1 + α(n-α)

    which simplifies to
    
    -1/2α^2 + (n-1/2)α - n2≥ 0.


    Let us now consider the left-hand side of the inequality (<ref>) as a polynomial h in α,
    treating n as a constant.
    The only roots of h are n-1 and n, and h(α) is nonnegative if and only if n-1≤α≤ n.
    Therefore, we must have α∈{n-1,n}.


    Now we show α≤β.
    As noted in the proof of Proposition <ref>,
    when (i,a) is an edge in G_E but not _2(G_E),
    we may solve a zero-dimensional quadratic system for x_ia given {m_ia: (i,a) ∈ E}.
    Thus we may now assume that G_E = _2(G_E) and allow E to be spanning in  (as opposed to a basis of ).
    

    Assume for the sake of contradiction that α > β.
    Then,
     the α+12 constraints f̃_ij = 0 where 1 ≤ i ≤ j ≤α
    together can contribute at most αβ-β2 to codimension.
    This is because for 1 ≤ i ≤ j ≤α,
    the polynomials from (<ref>) with k = β
    give the entries of an α×α symmetric matrix with rank at most β,
    and the dimension of the variety of α×α symmetric matrices of rank at most β is αβ-β2
    (see for example <cit.>).
    Also, as before, at least one of the constraints g̃_a = 0, 1 ≤ a ≤β is redundant.
    Since π_E^-1(π_E(M)) is zero-dimensional,
    we must have |F| ≤αβ-β2 + β -1
    and therefore
    
    α(β-1) - β2 - n2≥ 0.

    
    
    
    After plugging in n-1 for α,  (<ref>) becomes (β - n)^2 + n + β≤ 2,
    which is a contradiction because n ≥ 3.
    Plugging in n for α = n in
    (<ref>), we get the inequality -n-β≥ (β - n)^2,
    which is a contradiction because the left hand side is strictly negative, and the right hand side is nonnegative.
    Hence, we have α≤β.

    The final inequality β≤n2 + α - 1 follows from the fact that _2(G_E) has n2 + α + β - 1 edges
    and each of the β non-isolated column vertices has degree at least 2.










































§ DEGREE OF PROJECTION AND ALGEBRAIC IDENTIFIABILITY 


Now that we have a handle on which subsets E ⊆ [n]× [r]
yield projections π_E: →^E that are generically finite-to-one,
we can ask about the cardinality of a generically finite fiber.
In other words, we want to solve the following problem.
[Algebraic identifiability complexity]
Develop a combinatorial method for computing the degree of the map π_E:→^E
from G_E when E is a basis of .

The following theorem gets us part of the way towards a solution to Problem <ref>.



    Let r ≥ n+2 > 4 and let E ⊆ [n]× [r].
    Define F ⊆[n]× [r]  such that _2(G_E) = G_F,
    and let k denote the number of vertices that are isolated in _2(G_E) but not in G_E.
	If E is a spanning set of , then we have
	
    π_E=2^k ·π_F.



	First observe, E ⊆ F and so we have a projection map h: π_F() →^E
	that omits all the coordinates corresponding to elements of F ∖ E.
	Then we have π_E= h∘π_F and
    
    π_E=π_F · h,

    which can be seen as follows.
    The maps h: π_F() →^E and π_E: →^E are each branched covers of ^E.
     In other words, there exist dense Zariski open subsets U_1 and U_2 of ^E such that h restricted to h^-1(U_1) and π_E restricted to π_E^-1(U_2) are covering spaces.
     Moreover,  h and π_E restricted to U_1∩ U_2 are also covering spaces.
     Since π_E= h∘π_F, we have π_F is a homomorphism of covering spaces and thus
     the topological degree of the restricted maps with image U_1∩ U_2 satisfy π_E=π_F · h. As U_1 and U_2 are  dense Zariski open subsets of ^E, we have U_1∩ U_2 is also a dense Zariski open subset of ^E. Therefore, the equality above follows.

    It now suffices to show h = 2^k.
    Let M ∈ be generic and
    define g̃_a and f̃_ij as in the proofs of Theorem <ref> and Proposition <ref>.
    We can order the elements of F∖ E as (i_1,a_1),…,(a_k,i_k)
    such that for each j ∈{1,…,k},
    the only non-x_i_j a_j variables in at least one of g_a_j or f_i_ji_j will be of the form x_i_la_l with l < j.

    Let  denote the system of all such polynomials.
    The non-constant coordinates of h^-1(π_E(M)) are given by the variety defined by the vanishing of .
    
    By solving  via “back-substitution” in the order x_a_1i_1,…,x_a_ki_k,
    we see that this variety has exactly 2^k points.
    Thus, | h^-1(f(M))|=2^k and h=2^k.


Let E ⊆ [n]× [r] with E a basis of 
and define F ⊆ [n] × [r] so that  G_F = _2(G_E).
Let β denote the number of column vertices in _2(G_E)
and let M ∈ be generic whose (i,a) entry is m_ia.
If r ≥ n+2 > 4 and r ≥β+1,
then the degree of the projection map π_F: →^F only depends on _2(G_E) and not on r.
This follows from the fact that if r ≥β+1,
then the set of non-constant polynomials f̃_ij and g̃_a obtainable by substituting x_ia = m_ia
for (i,a) ∈ F does not depend on r.
So for a graph H such that H = _2(G_E) for some basis E of ,
let (H) denote the degree of π_F when r ≥β+1.

If r = β (r < β is not possible),
then (π_F) ≤(_2(G_E)).
Thus Theorem <ref> gives us the bound (π_E) ≤ 2^k (_2(G_E)).

Theorem <ref> tells us, that for fixed n,
there are only finitely many _2(G_E).
Thus one can compute all values of (_2(G_E)) for a fixed n
and use this to produce an algorithm that bounds the size of a finite fiber |π_E^-1(π_E(M))|
by computing the 2-core of G_E. This is done in Algorithm <ref>
and Example <ref> illustrates this for the case n = 3.








When E is a basis of X_3,r,
_2(G_E) is one of seven graphs, displayed in Figure <ref>.
For each possible _2(G_E), we compute the cardinality of a projection of an X_3,r onto _2(G_E)
using probability-one methods in  <cit.> via  <cit.>
When _2(G_E) has five or more column vertices, we took r = 5 and r = 6
and observed that in both cases, the degree of projection was the same.
When _2(G_E) has fewer than five column vertices, we take r = 5.
These degrees are given in Table <ref>.
Via the above discussion, this characterizes the possible degrees of a projection of X_3,r onto a basis.
For example, if E ⊆ [3]×[5]
where as a zero-one matrix,

    E=[ 0 0 0 0 0; 1 1 0 0 0; 1 1 1 0 0;   ],

then the degree of a generic fiber of this projection is 128=2^2· 32.
This can be read off from Table <ref>
by noting that F such that G_F = _2(G_E) is given in the top row of the table and the degree of the corresponding fiber is 32.











§ ACKNOWLEDGMENTS

We are very thankful for the reviewers' comments to improve this article. 
This work was partially supported by the grants NSF CCF-1708884 and NSA H98230-18-1-0016.
Daniel Irving Bernstein was supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship (DMS-1802902).
He also completed some of this work while employed by the NSF-supported (DMS-1439786)
Institute for Computational and Experimental Research in Mathematics in Providence, RI,
during the Fall 2018 semester program on nonlinear algebra.
Cameron Farnsworth's research was supported in part by the National Research Foundation of Korea (Grant Number 20151009350).
Jose Israel Rodriguez was partially supported by the College of Letters and Science, UW-Madison.

abbrv



