finding components of a linear matroid

[Dima Pasechnik]

Dear all,

is there anything to know on this topic, apart from
that one needs (or not?!) to find a basis, something that
would need O(mn^2) operations for a matroid of m vectors in R^n,
decompose each vector in this basis, and look at non-zero coordinates?

Is there anything more clever than that?

Thanks,
Dima

[Stefan van Zwam]

That's pretty much it, as far as I'm aware. I'd formulate it slightly differently:

Find a basis
Find the B-fundamental circuit of each remaining element
Put this information in a B x (E-B) matrix with zeroes and ones.
Components of matroid = components of associated bipartite graph.


--Stefan.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "sage-matroid" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Rudi Pendavingh]

The bottleneck seems to be pivoting in the representing matrix to get that identity matrix somewhere.

But two elements of the matroid are in the same component if(f) there is some circuit containing them both. So how is your matroid stored? If the representing matrix is sparse, you could go and find any circuit, then contract it to a single element, rinse and repeat. That may be faster.

Rudi

[Dima Pasechnik]

On 2014-03-10, Rudi Pendavingh <rudi.pe...@gmail.com> wrote:
> The bottleneck seems to be pivoting in the representing matrix to
> get that identity matrix somewhere.
>
> But two elements of the matroid are in the same component if(f)
> there is some circuit containing them both. So how is your matroid
> stored? If the representing matrix is sparse, you could go and find
> any circuit, then contract it to a single element, rinse and repeat.

well, it's a theory question. We have a matrix in some basis, not
necessarily sparse.

Dima

[Rudi Pendavingh]

> On 10 mrt. 2014, at 23:15, Dima Pasechnik <dim...@gmail.com> wrote:
>
> well, it's a theory question. We have a matrix in some basis, not
> necessarily sparse.

In that case, you're done in linear time (that is O(nm)) doing as Stefan suggested. You can't beat reading the input, so that is optimal.
--Rudi

[Dima Pasechnik]

But how can one find a basis in linear time? Don't you need to do
reductions of vectors modulo a subbasis found so far?
(which is O(n^2) if you far enough in building the full basis)

And you might have to do this for O(m) vectors, before, say, the
last basis element is found. Naively this seems to give
O(mn^2).

Dima

> --Rudi
>

[Rudi Pendavingh]

Hi Dima,

I misread your statement

>>> We have a matrix in some basis, not necessarily sparse.

and thought it meant that your matrix was already of the form [ I A ]. Once you have this form, it's linear time, but I agree that getting there takes O(n^2m) time in a non-sparse matrix.

--Rudi

> But how can one find a basis in linear time? Don't you need to do
> reductions of vectors modulo a subbasis found so far?
> (which is O(n^2) if you far enough in building the full basis)
>
> And you might have to do this for O(m) vectors, before, say, the
> last basis element is found. Naively this seems to give
> O(mn^2).
>
> Dima
>
>> --Rudi
>>
>

[Dima Pasechnik]

On Tuesday, 11 March 2014 10:06:23 UTC, Rudi Pendavingh wrote:

I misread your statement
>>>  We have a matrix in some basis, not necessarily sparse.
and thought it meant that your matrix was already of the form [ I A ]. Once you have this form, it's linear time, but I agree that getting there takes O(n^2m) time in a non-sparse matrix.

there is in fact an improvement to O(n^{w-1}m), where w is the best exponent for matrix multiplication, see
Thm 2 in  "A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid",
http://dx.doi.org/10.1007/3-540-45471-3_21

(not that it is too surprising...)

Dima