CODEWITHSUNDEEP
matlabmatrix
0x0
0x0

Reputation: 3075

Generating linear combination of a matrix

I want to create a matrix A [4x8] as follows.

The matrix A always has 1 as its diagonal. A11,A22,A33,A44 = 1

This matrix can be considered as two halves with first half being the first 4 columns and the second half being the second 4 columns like something below : 

        1 -1 -1 -1   1 0 0 1
  A =  -1  1 -1  0   0 1 0 0
       -1 -1  1  0   1 0 0 0 
       -1 -1 -1  1   1 1 0 0

Each row in the first half can have either two or three -1's:

The overall objective is to have the sum of each row to be 0. I need to generate all possible combinations of a matrix like this.

It will be better if the matrix with new combination be created at each iteration so that after using it I can discard it or else storing all the combinations is very space intensive. Can anybody help me ?

one possible solution I could think of is to generate all possible combinations of row1, row2, row3 and row4 and create a matrix in each iteration. Does that look feasible?

Upvotes: 2

Views: 2688

Answers (2)

gnovice
gnovice

Reputation: 125854

Here's one possible solution. If you ignore the diagonal ones for the moment, you can generate all possible patterns for the other 7 values using the functions KRON, REPMAT, PERMS, UNIQUE, EYE, and ONES:

>> rowPatterns = [kron(eye(3)-1,ones(4,1)) ...      %# For 2 out of 3 as -1
                  repmat(eye(4),3,1); ...           %# For 1 out of 4 as 1
                  repmat([-1 -1 -1],6,1) ...        %# For 3 out of 3 as -1
                  unique(perms([1 1 0 0]),'rows')]  %# For 2 out of 4 as 1

rowPatterns =

     0    -1    -1     1     0     0     0
     0    -1    -1     0     1     0     0
     0    -1    -1     0     0     1     0
     0    -1    -1     0     0     0     1
    -1     0    -1     1     0     0     0
    -1     0    -1     0     1     0     0
    -1     0    -1     0     0     1     0
    -1     0    -1     0     0     0     1
    -1    -1     0     1     0     0     0
    -1    -1     0     0     1     0     0
    -1    -1     0     0     0     1     0
    -1    -1     0     0     0     0     1
    -1    -1    -1     0     0     1     1
    -1    -1    -1     0     1     0     1
    -1    -1    -1     0     1     1     0
    -1    -1    -1     1     0     0     1
    -1    -1    -1     1     0     1     0
    -1    -1    -1     1     1     0     0

Note that this is 18 possible patterns for any given row, so your matrix A can have 18^4 = 104,976 possible row patterns (quite a bit). You can generate every possible 4-wise row pattern index by using the functions NDGRID, CAT, and RESHAPE:

[indexSets{1:4}] = ndgrid(1:18);
indexSets = reshape(cat(5,indexSets{:}),[],4);

And indexSets will be a 104,976-by-4 matrix with each row containing one combination of 4 values between 1 and 18, inclusive, to be used as indices into rowPatterns to generate a unique matrix A. Now you can loop over each set of 4-wise row pattern indices and generate the matrix A using the functions TRIL, TRIU, EYE, and ZEROS:

for iPattern = 1:104976
  A = rowPatterns(indexSets(iPattern,:),:);  %# Get the selected row patterns
  A = [tril(A,-1) zeros(4,1)] + ...          %# Separate the 7-by-4 matrix into
      [zeros(4,1) triu(A)] + ...             %#   lower and upper parts so you
      [eye(4) zeros(4)];                     %#   can insert the diagonal ones
  %# Store A in a variable or perform some computation with it here
end

Upvotes: 5

Amro
Amro

Reputation: 124563

Here is another solution (with minimal looping):

%# generate all possible variation of first/second halves
z = -[0 1 1; 1 0 1; 1 1 0; 1 1 1]; n = -sum(z,2);
h1 = {
    [         ones(4,1) z(:,1:3)] ;
    [z(:,1:1) ones(4,1) z(:,2:3)] ;
    [z(:,1:2) ones(4,1) z(:,3:3)] ;
    [z(:,1:3) ones(4,1)         ] ;
};
h2 = arrayfun(@(i) unique(perms([zeros(1,4-i) ones(1,i)]),'rows'), (1:2)', ...
    'UniformOutput',false);

%'# generate all possible variations of complete rows
rows = cell(4,1);
for r=1:4
    rows{r} = cell2mat( arrayfun( ...
        @(i) [ repmat(h1{r}(i,:),size(h2{n(i)-1},1),1) h2{n(i)-1} ], ...
        (1:size(h1{r},1))', 'UniformOutput',false) );
end

%'# generate all possible matrices (pick one row from each to form the matrix)
sz = cellfun(@(M)1:size(M,1), rows, 'UniformOutput',false);
[X1 X2 X3 X4] = ndgrid(sz{:});
matrices = cat(3, ...
    rows{1}(X1(:),:), ...
    rows{2}(X2(:),:), ...
    rows{3}(X3(:),:), ...
    rows{4}(X4(:),:) );
matrices = permute(matrices, [3 2 1]);              %# 4-by-8-by-104976

%#clear X1 X2 X3 X4 rows h1 h2 sz z n r

Next you can access the 4-by-8 matrices as:

>> matrices(:,:,500)
ans =
     1    -1    -1    -1     0     1     0     1
    -1     1    -1     0     0     0     1     0
     0    -1     1    -1     0     0     1     0
     0    -1    -1     1     0     0     0     1

We could also confirm that all rows in all matrices sum to zero:

>> all(all( sum(matrices,2)==0 ))
ans =
     1

Upvotes: 2

Related Questions