On choosing the elements of a matrix
Sayaka Fujisaki
familiar to anyone? Thank you in advance!
I am choosing the elements of an m x n matrix, A, with m > n. We can
write A as [A1; A2], where A1 has size k x n and A2 has size (m-k) x
n. I have free choice over the elements of A, except for constraints
of the form A[i1,j1] = A[i2,j2], for various indices i1, i2, j1, j2,
with i1 <= k and i2 > k (in other words, certain elements of A1 must
always be equal to certain corresponding elements of A2). My goal is
to determine if there exists an assignment of elements to A, obeying
these constraints, in such a way that the rows of A1 have full rank
and are linearly independent from the rows of A2. Does anyone have
any suggestions for possible directions on this?
Thank you! SF
PS I'm working with matrices with entries in Z/2, if that complicates/
simplifies things...
Peter Spellucci
In article <9df3e309-b952-42cb...@j4g2000yqe.googlegroups.com>,
I feel your concept of "the rows of A1 should be linearly independent
from the rows of A2" is incorrect:
you may have for example a 4 by 3 matrix , clearly of rank 3 at most,
with exact rank 3, such that any three rows define an invertible matrix.
taht means any of the rows can be expressed by the other three.
what you mean is this???
A1'*x1 + A2'*x2 = 0 implies x1=0 .' denotes transposition
but has a nontrivial solution set?
this would mean
inverse(A1*A1')*A1*A2'*x2 =0 = -x1
has nontrivial solutions (the inverse exists since A1 has full row rank)
and hence requires that the
k times m-k matrix A1*A2'
is rank deficient, given the additional constraints . this might be possible
for example with
m=5, n=3; k=3;
A1= [1 0 1 ; 0 1 1 ; 0 -1 1]
and
A[1,1]=A[4,2]; A[2,1]=A[4,1]; A[3,3]=A[5,3]
one gets
A2= [0 1 1 ; 0 1 1]
as the solution.
But I see no simple way to derive sufficient conditions for this in general.
hth
peter
Chip Eastham
Hi, SF:
I don't recognize the problem but it is familiar territory.
If I understand the problem, having full rank for the k
rows of A1 will be facilitated by having minimal rank in
A2, in that the rows of A1 must lie outside the row
space of A2.
I guess I would tackle the problem as a search using
backtracking software like Prolog to seek a solution.
Using matrix entries in Z/2Z certainly simplifies things
like checking for linear independence. Are you looking
for an "analytic" solution or (as the newsgroup choice
suggests) a "computational" one.
regards, chip
Sayaka Fujisaki
> what you mean is this???
>
> A1'*x1 + A2'*x2 = 0 implies x1=0 .' denotes transposition
I do actually require that the row spans be independent. In your 4 x
3 example, the solution would be "no such solution exists, even if
there are no constraints". In fact, by your reasoning, if k >= n
(where k is the number of rows of A1), then the situation I've
described is impossible, even if there are no constraints at all,
because A1 would have rank n, and hence its rows span R^n. Hence, a
necessary condition for a solution to exist is that k < n. So, A1
must have rank k, and therefore the rank of A2 cannot exceed n-k.
> If I understand the problem, having full rank for the k
> rows of A1 will be facilitated by having minimal rank in
> A2, in that the rows of A1 must lie outside the row
> space of A2.
>
> I guess I would tackle the problem as a search using
> backtracking software like Prolog to seek a solution.
> Using matrix entries in Z/2Z certainly simplifies things
> like checking for linear independence. Are you looking
> for an "analytic" solution or (as the newsgroup choice
> suggests) a "computational" one.
What I'm most interested in is a set of sufficient conditions (on the
constraint set and on m,n,k) that guarantee that a solution exists.
The "big picture" is to maximize n, given m and k, but for the moment
I'm just curious if there are easy conditions under which we have a
guaranteed solution. For example, it is clear that if one of the
constraints says that a row of A2 is equal to a row of A1 (i.e. A1
[i1,j] = A2[i2,j] for all j), then certainly no solution exists. I'm
trying to find a way to "describe" these constraints so as to
generalize the preceding notion.
Thank you! SF
Chip Eastham
> I do actually require that the row spans be independent.
This is a stronger condition than you previously posed,
as I understood it, merely requiring that no row of A1
belong to rowspace(A2). If I grasp the new condition:
rowspace(A1) /\ rowspace(A2) = {0}
Here's one condition that guarantees a solution will
exist: Let pi:{1,..,k} -> {1,..,n} be a mapping of
row to column indexes s.t. {(i,pi(i) | i=1,..k } is
disjoint from the set of entries in A1 involved in
"constraints" (equated to entries in A2).
Given such a mapping we set A(i,pi(i)) = 1 for all
i=1,..,k and otherwise entries of A are to be zero:
A =
[ A1 ] <- k rows by n columns
[ A2 ] <- m-k rows by n columns
regards, chip
Chip Eastham
I should not have omitted that the mapping pi is 1-1,
i.e. that distinct rows 1,..,k map to distinct columns.
Sorry for any confusion!
--c
Sayaka Fujisaki
assigning the non-constrained entries. That makes sense, I hadn't
thought of that!
One matrix I'm interested is those of the following form (fixed-width
font may be preferable)
n1 n2
__________________________
| | |
| | |
| Y | X | k = m/2
| | |
|________|________________|
| | |
| | |
| X | Z | k = m/2
| | |
|________________|________|
I'm not familiar with matrices of this shape in anything I've read.
Here A1 = [Y,X], A2 = [X,Z], and n1 + n2 = n. The "un-constrained
entries" that you describe are the entries of Y, so we can certainly
make a compatible set if k <= n1. One thing I noticed is that if n1
is odd, then we can find a valid assignment for k <= ceil(n/2) by
filling in only the odd columns of the matrix A1 = [Y,X], because then
only the even columns of A2 = [X,Z] are nonzero. One can also do this
"striping" procedure for even n1, by filling in blocks of two columns
at a time, etc., but I don't know if these kinds of patterns are
optimal or not and I'm curious if they can be generalized nicely.
Thank you! SF
Chip Eastham
> Ah, I see; so what you're doing is defining the matrix by only
> assigning the non-constrained entries. That makes sense, I hadn't
> thought of that!
> One matrix I'm interested is those of the following form (fixed-width
> font may be preferable)
>
> n1 n2
> __________________________
> | | |
> | | |
> | Y | X | k = m/2
> | | |
> |________|________________|
> | | |
> | | |
> | X | Z | k = m/2
> | | |
> |________________|________|
>
> I'm not familiar with matrices of this shape in anything I've read.
> Here A1 = [Y,X], A2 = [X,Z], and n1 + n2 = n. The "un-constrained
> entries" that you describe are the entries of Y, so we can certainly
> make a compatible set if k <= n1. One thing I noticed is that if n1
> is odd, then we can find a valid assignment for k <= ceil(n/2) by
> filling in only the odd columns of the matrix A1 = [Y,X], because then
> only the even columns of A2 = [X,Z] are nonzero. One can also do this
> "striping" procedure for even n1, by filling in blocks of two columns
> at a time, etc., but I don't know if these kinds of patterns are
> optimal or not and I'm curious if they can be generalized nicely.
>
> Thank you! SF
Hi, SF:
Originally you asked about the case m > n, which
means in the context of the restrictive cases as
above that 2k > n. We can derive a necessary
condition for rank(A1) = k and the rowspaces of
A1,A2 to have trivial intersection if m > n:
n1 >= m - n = 2k - n
Proof: Let A be the matrix A1 over A2.
0 = dim(rowspace(A1) /\ rowspace(A2))
= dim(rowspace(A1)) + dim(rowspace(A2)
- dim(rowspace(A1) + rowspace(A2))
= rank(A1) + rank(A2) - rank(A)
Now rank(A1) = k by assumption, so that since
A1 = [Y X] and rank(Y) <= n1, rank(X) >= k-n1.
Thus, as A2 = [X Z]:
rank(A2) >= rank(X) >= k-n1
and finally rank(A) <= n. Combining these:
0 >= k + (k-n1) - n
from which it follows n1 >= 2k - n. QED
Conjecture: A variation of the "striping"
construction outlined by SF will succeed if
n1 >= 2k - n > 0, making this a sufficient
as well as necessary condition in the
simplified problem.
regards, chip
Chip Eastham
> On Dec 4, 6:32 pm, Sayaka Fujisaki <psychoblad...@hotmail.com> wrote:
> > One matrix I'm interested is those of the following form
> > (fixed-width font may be preferable)
> > n1 n2
> > __________________________
> > | | |
> > | | |
> > | Y | X | k = m/2
> > | | |
> > |________|________________|
> > | | |
> > | | |
> > | X | Z | k = m/2
> > | | |
> > |________________|________|
> Conjecture: A variation of the "striping"
> construction outlined by SF will succeed if
> n1 >= 2k - n > 0, making this a sufficient
> as well as necessary condition in the
> simplified problem.
Referring to the upper half matrix as A1 = [Y|X]
and the lower half matrix as A2 = [X|Z], we ask
that rowspace(A1) and rowspace(A2) have trivial
intersection, and that A1 be of "full-rank".
Unless the X blocks are empty (n2 = 0), it is
impossible for A1 to be of full column rank, for
if rank(A1) = n and rank(A1) >= rank(X) = n2 > 0,
then clearly rowspace(A1) /\ rowspace(A2) is
nontrivial, i.e. rowspace(A2). This actually
shows that rank(A1) < n, provided n2 > 0.
On the other hand if n1 = 0, then rowspace(A1)
and rowspace(A2) are both equal to rowspace(X),
so that only when X = 0 is their intersection
trivial.
So we can assume n1,n2 > 0 and also that "full-
rank" for A1 means rank k (full row-rank).
Indeed the problem can then be reframed as what
is the maximum row rank k of A1, given the
trivial intersection of rowspaces of A1 and A2,
since if A1 has rank k, then some subset of k
rows of A1 are independent when k < n. In this
form we ask what value K(n1,n2) the maximum rank
of A1 is, given n1,n2 > 0 and trivial intersection
of rowspace(A1) and rowspace(A2).
Then as in my conjecture above:
K(n1,n2) = n1 + floor(n2/2)
That is, n1 >= 2k - (n1+n2) is "tight" when
k = K(n1,n2) = n1 + floor(n2/2), subject to
the integrality of k.
The striping technique as Sayaka originally
outlined works for n1 = 1, but does not get
us the maximum rank k in many cases n1 > 1,
even if n1 is odd.
For example, n1 = 3 and n2 = 1 has "striping"
construction:
1 0 0 | 0
0 0 1 | 0
-------------
0 | 0 0 0
0 | 0 0 0
in which rank(A1) = 2. But K(3,1) = 3 is
optimal:
1 0 0 | 0
0 1 0 | 0
0 0 1 | 0
-------------
0 | 0 0 0
0 | 0 0 0
0 | 0 0 0
Nor is this phenomenon limited to n1 > n2.
When n1 = 3 and n2 = 5, striping looks like:
1 0 0 | 0 0 0 0 0
0 0 1 | 0 0 0 0 0
0 0 0 | 0 1 0 0 0
0 0 0 | 0 0 0 1 0
-----------------------------
0 0 0 0 0 | 0 0 0
0 0 0 0 0 | 0 0 0
0 1 0 0 0 | 0 0 0
0 0 0 1 0 | 0 0 0
which has rank(A1) = 4, but K(3,5) = 5 is
attainable:
1 0 0 | 0 0 0 0 0
0 1 0 | 0 0 0 0 0
0 0 1 | 0 0 0 0 0
0 0 0 | 0 0 0 1 0
0 0 0 | 0 0 0 0 1
-----------------------------
0 0 0 0 0 | 0 0 0
0 0 0 0 0 | 0 0 0
0 0 0 0 0 | 0 0 0
0 0 0 1 0 | 0 0 0
0 0 0 0 1 | 0 0 0
These examples might suggest that Z = 0
can be assumed, but such is not the case.
Consider K(3,2) = 4:
1 0 0 | 0 0
0 1 0 | 0 0
0 0 1 | 0 0
0 0 0 | 1 0
-----------------
0 0 | 0 0 0
0 0 | 0 0 0
0 0 | 0 0 0
1 0 | 0 0 1
and it is not hard to show rank(A1) = 4
cannot be achieved with Z = 0.
regards, chip
Chip Eastham
Regarding my conjecture:
> Conjecture: A variation of the "striping"
> construction outlined by SF will succeed if
> n1 >= 2k - n > 0, making this a sufficient
> as well as necessary condition in the
> simplified problem.
A modified "striping" construction:
Let k = n1 + floor(n2/2) for n1,n2 > 0.
Let n2 be divided by 2*n1, with quotient q and
remainder r:
n2 = (2*n1)*q + r
Since the divisor is even, we also have:
floor(n2/2) = n1*q + floor(r/2)
Let B = [0 I] be an n1 x 2*n1 matrix, and assign
entries from Z/2Z to Y,X,Z as follows (I is an
identity matrix of the appropriate size wherever
it appears):
Y = [ I ] is a k x n1 matrix;
[ 0 ]
X = [ 0 ] is a k x n2 matrix
[ M ]
where M =
[ B 0 ... 0 0 ] \
[ 0 B ... 0 0 ] | q copies of
: : | B
[ 0 0 ... B 0 ] /
[ 0 0 ... 0 C ]
is floor(n2/2) x n2, and C = [I 0] is floor(r/2) x r;
Z = [ 0 0 ]
[ 0 I ]
is a k x n2 matrix whose identity block is the same
size as in C above, namely floor(r/2) x floor(r/2).
Sketch of proof: One finds that the shifted X in A2
overlaps in nonzero columns only through the shifted
block C, and the nonzero entries in Z are the same
rows as that shifted block C in A2, thereby avoiding
any nontrivial intersection between rowspace(A1) and
rowspace(A2). Note in particular there's no overlap
between nonzero columns of Z and the nonzero columns
of C in A1 above it, since floor(r/2)+floor(r/2)<=r.
regards, chip
Sayaka Fujisaki
is quite elegant! I have some more thoughts that I would like to post
shortly.
Thanks, SF