Re: a linear algebra problem

shuqin.fan@xxxxxxxxx writes:

For any given $2^{n-1}$ number of vectors of dimension $n$ over
$GF(2)$
with zero vector in it , what is the maxmium dimension of the linear
subspace contained in It ?

For Example: If it is a $n-1$ linear subspace, the maximun dimension
is n-1.


But if it is artbitarily given, what is the maximum dimension?

It could be anything from 1 to n-1. To get an example where the maximum
dimension is 1, take the set S consisting of 0 and any 2^(n-1)-1 of the
2^(n-1) vectors v such that sum_j v_j is odd. Note that for any two
distinct nonzero members a and b of S, a+b is not in S.

Given an arbitrary set S containing 0, the problem of finding a linear
subspace of S with maximum dimension can be written as a
maximum-independent-set problem in a graph. Namely, let G be the graph whose
vertices are the nonzero members of S, with edges joining vertices a and b
such that a+b is not in S.
If T is an independent set in this graph, i.e. no two members of T are joined
by an edge, then T union {0} is a linear subspace of S. Now
maximum-independent-set is an NP-complete problem. I don't know if this
special case of maximum-independent-set problems is NP-complete, but I
wouldn't be surprised if it is. If so, it's not going to be easy to determine
the maximum dimension for an arbitrary S.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Re: rank([X;Y]) < rank(X) + rank(Y)
    ... spanX contains all possible linear combinations of the ... It is an entire subspace, ... vectors in a vector space of dimension 45. ... Any point in the row space ...
    (comp.soft-sys.matlab)
  • Re: ? dual spaces
    ... A's domain and of say 3 dimension must have a subspace V of A's codomain ... If A is a linear operator defined on a finite dimensional ...
    (sci.math)
  • a linear algebra problem
    ... with zero vector in it, what is the maxmium dimension of the linear ... If it is a $n-1$ linear subspace, ...
    (sci.math)
  • A linear algebra problem?
    ... For any given $2^$ number of vector of dimension $n$ over $GF$ ... with zero vector in it, what is the least dimension of the linear ... If it is a $n-1$ linear subspace, ...
    (sci.math)
  • Re: Symmetry
    ... space, along which, for instance, fn, would be a compact linear ... which would a simply converge along one linear compact ... are true in any dimension. ... is being applied to instances of reals. ...
    (sci.physics.relativity)