Given a spanning set, consider the minimum number of vectors that you must remove in order to make it no longer span. What is this number called?

If the vectors are columns in a matrix $\Phi$, then this number can be expressed as $$ \min\|\Phi^*x\|_0\quad\mbox{s.t.}\quad x\neq0. $$ This seems like a sort of dual of spark, which is the minimum size of a dependent set, i.e., $$ \min\|x\|_0\quad\mbox{s.t.}\quad \Phi x=0,~x\neq0. $$ Has "co-spark" been studied in linear algebra, matroid theory, etc.?


I don't know if this deserves to be an answer or a comment, as it includes information you surely know.

The terminology of matroid theory borrows heavily from graph theory, linear algebra, and other fields. A dependent set in a graphic matroid corresponds to a cycle in the underlying graph, so a general dependent set in a matroid is called a circuit. The length of the smallest cycle of a graph is its girth, so the same word is used for a general matroid. As you're well aware, the spark of a matrix is the girth of its corresponding vector matroid.

You're correct that your notion appear to be dual to spark. The appropriate terminology here could have been "cutset", as that's the corresponding notion in a (connected) graph, but for consistency it's cogirth. The co-spark of a matrix is the cogirth of its corresponding vector matroid.

A matroid is representable (ie, as a vector matroid) over a field if and only if its dual matroid is representable. Moreover, the transformation taking a representation of a vector matroid to a representation of its dual matroid is completely effective. It follows, in a sense, that studying the co-spark of a matrix is equivalent to studying the spark of another matrix. In particular, any computational hardness results for spark carry over to co-spark. It seems, then, that the notion of co-spark would be useful primary as terminology and as a way of getting a handle on things, but not actually for new ideas.

Here's one paper that has explicitly looked into these sorts of things: On the (co)girth of a connected matroid.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.