CODEWITHSUNDEEP
arraysmatlabmatrix
lesspritfree
lesspritfree

Reputation: 23

How can I generate this matrix (containing only 0s and ±1s)?

I would like to generate matrix of size (n(n-1)/2, n) that looks like this (n=5 in this case):

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

This is what I, quickly, came up with:

G = [];
for i = 1:n-1;
   for j = i+1:n       
        v = sparse(1,i,-1,1,n);
        w = sparse(1,j,1,1,n);
        vw = v+w;
        G = [G; vw];        
    end
end

G = full(G);

It works, but is there a faster/cleaner way of doing it?

Upvotes: 2

Views: 69

Answers (2)

Luis Mendo
Luis Mendo

Reputation: 112689

Use nchoosek to generate the indices of the columns that will be nonzero:

n = 5; %// number of columns
ind = nchoosek(1:n,2); %// ind(:,1): columns with "-1". ind(:,2): with "1".
m = size(ind,1);
rows = (1:m).'; %'// row indices
G = zeros(m,n);
G(rows + m*(ind(:,1)-1)) = -1;
G(rows + m*(ind(:,2)-1)) = 1;

Upvotes: 1

Mikhail
Mikhail

Reputation: 21749

You have two nested loops, which leads to O(N^2) complexity of non-vectorized operations, which is too much for this task. Take a look that your matrix actually has a rectursive pattern:

G(n+1) = [ -1  I(n)]
         [  0  G(n)];

where I(n) is identity matrix of size n. That's how you can express this pattern in matlab:

function G = mat(n)
  % Treat original call as G(n+1)
  n = n - 1;

  % Non-recursive branch for trivial case
  if n == 1
    G = [-1 1];
    return;
  end

  RT = eye(n);                 % Right-top: I(n)
  LT = repmat(-1, n, 1);       % Left-top: -1
  RB = mat(n);                 % Right-bottom: G(n), recursive
  LB = zeros(size(RB, 1), 1);  % Left-bottom: 0

  G = [LT RT; LB RB];
end

And it gives us O(N) complexity of non-vectorized operations. It probably will waste some memory during recursion and matrix composition if Matlab is not smart enought to factor these out. If it is critical, you may unroll recursion into loop and iteratively fill up corresponding places in your original pre-allocated matrix.

Upvotes: 0

Related Questions