On May 24, 3:04 am, matt <n...@none.com> wrote:
> On 05/23/2011 12:25 AM, Daniel Lichtblau wrote:
>
>
>
>
>
>
>
>
>
> > On May 22, 6:19 am, matt<n...@none.com> wrote:
> >> Dear all,
>
> >> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
> >> where B1 is pxr and B2 is qxr.
>
> >> Now, consider the case in which another basis of null(A) exists that can
> >> be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
> >> C12 is pxu, C22 is qxu and C23 is qxv.
>
> >> Is there any algorithm which, when possible, returns
> >> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>
> >> I've tried to implement an algorithm which relies on rref and lu
> >> factorization, but I have some test cases in which it doesn't work.
>
> >> Is it reasonable to expect to solve this problem? Can you provide some
> >> suggestions?
>
> >> Thanks in advance
>
> >> 
> >> Matteo
>
> > Will depend on dimensions. Your t should be perhaps p, or at least not
> > larger, for example.
>
> > This might be along the lines you seek. I'll show an example with
> > Mathematica but
> > the code should translate readily to Matlab or other languages.
>
> Dear Daniel,
>
> first of all, thanks for time you took to reply.
>
> Unfortunately, I'm not familiar with Mathematica and I may have missed
> some crucial piece of your algorithm, but at first (also 2nd and 3rd)
> glance, it looks like the approach I've used too.
>
> I have a test case where my approach fails. I'd greatly appreciate if
> you could do the test with your algorithm; in case you managed it to
> work, I'll further investigate your approach to discover the differences
> with mine.
>
> Thanks in advance,
>
> Matteo.
>
> ========================================================================
> TEST CASE
> =========
>
> Let A be the following 16x18 matrix:
>
> A = [0.15005,0.4318,0.4318,0,0,0,0,0,0,0,0,0,1,0,0,0,0.4318,0.15005;...
> 0.0479,0,0,0,0,0,0,0.5,0,0,0,0,0,1,0,0.4318,0,0.0479;...
> 0,0.0479,0.4797,0,0,0,0,0,0,0,0,0,0,0,1,0.15005,0.0479,0;...
> 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0;...
> 0.0682,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0.0682;...
> 0,0.0682,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0.0682,0;...
> 0,0,0,0.15005,0,0,0,0,0,0,0,0,1,0,0,0,0,0.15005;...
> 0,0,0,0.2521,0,0,0,0,0,0,0,0,0,1,0,0,0,0.2521;...
> 0,0,0,0,0.2521,0,0,0,0,0,0.1797,0,0,0,1,0.15005,0.2521,0;...
> 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0;...
> 0,0,0,0.2682,0,0,0,0,0,0,0,0,0,1,0,0,0,0.2682;...
> 0,0,0,0,0.2682,0,0,0,0,0,0,0,0,0,1,0,0.2682,0;...
> 0.8660254,0.5,0.5,0,0,0,0,0.8660254,0,0,0,0,0,0,0,0,0.5,0.8660254;...
> 0.5877853,0.8090170,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.8090170,0.5877853;...
> 0,0,0,0.5,0.8660254,0,0,0,0,0,0.8660254,0,0,0,0,0,0.8660254,0.5;...
> 0,0,0,0.8660254,0.5,0,0,0,0,0,0,0,0,0,0,0,0.5,0.8660254];
>
> and let B = [B1;B2] the following 18x7 matrix (p = 7, q = 11, r = 7), a
> basis of A's kernel:
>
> B = [0.5773503,0,0,0,0,0,0;...
> 0,0.3970222,0.2780387,0.1320049,0.1183719,0.1097386,0.2343533;...
> 0,0,0,0,0,0,0;...
> 0.5773503,0,0,0,0,0,0;...
> 0,0.3970222,0.2780387,0.1320049,0.1183719,0.1097386,0.2343533;...
> 0,0.4674929,0.1645678,0.0222354,0.0918726,0.3672059,0.7814043;...
> 0,0.4589534,0.5071254,0.1336586,0.6822599,0.0935152,0.2002428;...
> 0,0,0,0,0,0,0;...
> 0,0.2514693,0.6927794,0.2576987,0.6159429,0.1043717,0.0114939;...
> 0,0.1813600,0.0081941,0.9260055,0.3112617,0.0760299,0.0830109;...
> 0,0,0,0,0,0,0;...
> 0,0.0424746,0.0617596,0.0739607,0.0881793,0.8964447,0.4213346;...
> 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,0;...
> 0,0.3970222,0.2780387,0.1320049,0.1183719,0.1097386,0.2343533;...
> 0.5773503,0,0,0,0,0,0];
>
> Actually, A has a precise physical meaning, and according to it I know
> that another basis of its null space exists in the form
> C = [C11, C12, 0; 0, C22, C23], where C11 is 7x2, C12 is 7x2,
> C22 is 11x2 and C23 is 11x3:
>
> C = [0, 0, 0, 0.5773503, 0, 0, 0;...
> 0, 0, 0.4616615, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0.5773503, 0, 0, 0;...
> 0, 0, 0.4616615, 0, 0, 0, 0;...
> 1, 0, 0.4883661, 0, 0, 0, 0;...
> 0, 1, 0.3355536, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0.0199593, 0, 0.3118486, 0.9413430, 0.1289331;...
> 0, 0, 0.0954459, 0, 0.9463925, 0.3197754, 0.0456604;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0.0004000, 0, 0.0842117, 0.1077822, 0.9906015;...
> 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, 0;...
> 0, 0, 0.4616615, 0, 0, 0, 0;...
> 0, 0, 0, 0.5773503, 0, 0, 0];
>
> Is your algorithm able to return C = [C11, C12, 0; 0, C22, C23], given
> B = [B1; B2] and p, q, and r?
>
> As I've said above, I've tried to play a lot with rref and lu
> factorization, but the best result I've got is
>
> D = [D11, 0; D21, D22], where D22 is 11x3 but is different from C23, and
> the remaining columns cannot reduced by rref().
>
>
>
>
>
>
>
>
>
> > Create a random 7x16 matrix.
>
> > mat = RandomReal[{10, 10}, {7, 16}];
>
> > Find, and row reduce, the null space.
>
> > nulls = NullSpace[mat];
> > rednulls = RowReduce[nulls];
>
> > We'll use p=4 and q=3.
>
> > p = 4;
> > q = Length[nulls]  p;
>
> > The bottom part, your [0,C22,C23] section, is easy.
>
> > bottom = Drop[rednulls, p];
>
> > We'll use the rest as our top part, and make alterations to get zeros
> > at the right end.
>
> > top = Take[rednulls, p];
>
> > From the description, you perhaps got this far. To do the rest, first
> > reverse the null vectors in 'bottom', row reduce, and reverse back. We
> > get a set of null vectors that is in echelon form columnwise from
> > righttoleft.
>
> > bottom2 = Map[Reverse, RowReduce[Map[Reverse, bottom]]];
>
> > Use this to zero the 'top' null vectors on the right side.
>
> > Do[top[[j]] = top[[j]]  top[[j, k]]*bottom2[[k]], {j,
> > Length[top]}, {k, Length[bottom2]}]
>
> > Here is the result in this example. Notice 'top' is now zerod on the
> > right.
>
> > In[116]:= top
>
> > Out[116]= {{1., 0., 0., 0., 0.1570521698815333, 0.1438145481730163,
> > 0.3341102247948281, 1.159540140238518, 0.2594884364079637,
> > 0.3116479687035286, 0.3244619655034073, 0., 0., 0., 0., 0.}, {0.,
> > 1., 0., 0., 0.353199257121722, 0.3955447462849144,
> > 0.2770180465857701, 1.051468466698785, 0.1646042200361716,
> > 1.289988509255458, 0.314174133729317, 0., 0., 0., 0., 0.}, {0., 0.,
> > 1., 0., 0.01528706008350322, 0.4786839021436973, \
> > 0.6380269892684085, 1.108257764338746, 0.4819835401333382,
> > 0.4796243014367019, 1.087136217299042, 0., 0., 0., 0., 0.}, {0.,
> > 0., 0., 1., 0.1905092618416806, 0.5196853394491601,
> > 0.756397394849917, 0.7050950551954204, 0.871705286441594, \
> > 0.9738372685877903, 0.8759900364217903, 0., 0., 0., 0., 0.}}
>
> > In[117]:= bottom
>
> > Out[117]= {{0, 0, 0, 0, 1, 0., 0., 0., 0., 0.5597664757073788,
> > 0.8143070871866038, 0.4277776146150173, 1.098944133145463,
> > 0.8081363401427031, 2.848613830703109, 1.872743300071011}, {0, 0,
> > 0, 0, 0, 1, 0., 0.,
> > 0., 0.4570234191081754, 0.1822057163418105, 1.020755390589715, \
> > 1.275200915927704, 0.4217003016771535, 0.3216906116940924,
> > 1.137607237636676}, {0, 0, 0, 0, 0, 0, 1, 0.,
> > 0., 2.057131526158108, 1.762612098425479,
> > 1.519296054797632, 1.391652167046286,
> > 0.3584888909059545, 3.946993942305765, 2.065619477936373}, {0, 0,
> > 0, 0, 0, 0, 0, 1, 0., 0.2846507307315486, 0.2895074106852998,
> > 0.4478459988247586, 1.530445195016555,
> > 1.163129348653568, 2.008261891031013, 1.445298232599805}, {0, 0, 0,
> > 0, 0, 0, 0, 0, 1,
> > 0.7013048464911343, 1.428978238780057, 1.569680138947566,
> > 0.4155594211966983, 1.988702096113409,
> > 0.9380405673096524, 1.404713184245211}}
>
> > We can check correctness by showing that the top and bottom are all
> > null vectors, and combine to have rank 9, the rank of the original
> > null space.
>
> > In[120]:= nullset = Join[top, bottom];
>
> > In[121]:= Max[Abs[mat.Transpose[nullset]]]
>
> > Out[121]= 1.332267629550188*10^14
>
> > In[122]:= MatrixRank[nullset]
>
> > Out[122]= 9
>
> > Daniel Lichtblau
> > Wolfram Research
I cannot replicate exactly the matrix you have in mind. Also I do not
have a clear idea of how the sizes work. But I can show something that
might be along the right lines for this particular matrix. First I'll
mention that I had misunderstood what is to be zeroed. So this new
code is slightly different from before.
I define 'mat' to be your matrix 'A' above, though in Mathematica
format.
mat = {{0.15005, 0.4318, 0.4318, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0.4318, 0.15005}, {0.0479, 0, 0, 0, 0, 0, 0, 0.5, 0, 0,
0, 0, 0, 1, 0, 0.4318, 0, 0.0479}, {0, 0.0479, 0.4797, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0.15005, 0.0479, 0}, {0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0.0682, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0.0682}, {0, 0.0682, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0.0682, 0}, {0, 0, 0, 0.15005,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0.15005}, {0, 0, 0,
0.2521, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0.2521}, {0, 0,
0, 0, 0.2521, 0, 0, 0, 0, 0, 0.1797, 0, 0, 0, 1, 0.15005,
0.2521, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0}, {0, 0, 0, 0.2682, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
0.2682}, {0, 0, 0, 0, 0.2682, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0.2682, 0}, {0.8660254, 0.5, 0.5, 0, 0, 0, 0, 0.8660254, 0,
0, 0, 0, 0, 0, 0, 0, 0.5, 0.8660254}, {0.5877853, 0.8090170, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.8090170, 0.5877853}, {0,
0, 0, 0.5, 0.8660254, 0, 0, 0, 0, 0, 0.8660254, 0, 0, 0, 0,
0, 0.8660254, 0.5}, {0, 0, 0, 0.8660254, 0.5, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0.5, 0.8660254}};
I will use Chop[] to remove small nonzero values. This is purely a
cosmetic touch.
nulls = NullSpace[mat];
rednulls = Chop[Map[Reverse, RowReduce[Map[Reverse, nulls]]]]
{{1., 0, 0, 1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 1., 0, 0, 1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 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, 1, 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},
{0, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
Mathematica gives the nulls as a list, that is to say, each row is a
null vector. You want the matrix which means switching, eventually, to
column form. But not until we do needed operations. I see that the
first two columns should have all zeros in the last 11 positions. So
I'll use the last two row reduced nulls for those, since they are the
ones with the most zeros at the end. (Why? Because I had reversed
nulls before row reducing, then reversed back.)
In[51]:= k = 2;
first = Take[rednulls, k]
last = Drop[rednulls, k]
Out[52]= {{0, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
Out[53]= {{1., 0, 0, 1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1}, {0, 1., 0, 0, 1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0,
0, 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, 1, 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}}
For the remaining five nulls we want some zeros at the end of three of
them (or as many as can be managed, I guess). That can be done with
the same reversereducereverse cycle.
In[49]:= last2 = Map[Reverse, RowReduce[Map[Reverse, last]]]
Out[49]= {
{1., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
1},
{0., 1., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
1, 0},
{0., 0., 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., 1, 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}}
Now form the matrix of transpose null vectors.
In[54]:= nullmat = Transpose[Join[first, last]]
Out[54]= {
{0, 0, 1., 0, 0, 0, 0},
{0, 0, 0, 1., 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 1., 0, 0, 0, 0},
{0, 0, 0, 1., 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, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0},
{0, 0, 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, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0}}
I think this has at least the correct zero submatrices.
Quick confirmation that it is a reasonable null matrix for 'mat'.
In[55]:= Max[Abs[mat.nullmat]]
Out[55]= 4.44089*10^16
I hope this gets you a bit closer.
Daniel Lichtblau
Wolfram Research
