Sparse matrix with diagonal zero and elements in every row/column

I'm trying to produce a sparse matrix that has zeros on the diagonal, but also has at least one element in each row and column.

With this code I get the first part, but I don't know how to make sure that each row and column have elements in them.

R = sprand(4,4,0.5);
r = 0 + (0.5 - 0)*rand(4,4);
A = full (R);
A(1:4+1:4*4)=0;
Nonz = nnz(A);
Diff = ceil(0.5*(4^2-4)) - Nonz;
B = find (A==0);
A=A';
B = find (A==0);
C = setdiff(B,1:4+1:4*4);
D = datasample(C,Diff,1,'Replace',false);
E=A;
for i = 1:length(D)
  E(D(i)) = 1;
end
E=E';
E(find(E)) = r(find(E));

[KL]

I'm trying to produce a sparse matrix that has zeros on the diagonal, but also has at least one element in each row and column ...

You already have that!?

>> A = 0 + (0.5 - 0)*rand(4,4)
A(1:4+1:4*4)=0

A =

      0.2947    0.0229    0.1600    0.4296
      0.4233    0.4000    0.4959    0.2969
      0.0890    0.3980    0.2755    0.4307
      0.1483    0.1979    0.0073    0.3885

A =

           0    0.0229    0.1600    0.4296
      0.4233         0    0.4959    0.2969
      0.0890    0.3980         0    0.4307
      0.1483    0.1979    0.0073         0

[Evelyn Salt]

Sorry, you are right, I messed something up. Now I edited my code and you can see that I get the matrix E which doesn't necessarily have elements in every row and column.

Answer 1

[Chris Perkins]

Hi Evelyn,

The code below shows how to compute a sparse square matrix where each row and column have at least one non-zero value, given a dimension size.

It computes a sparse matrix, and then tests for whether the matrix meets the row and column conditions, generating a new matrix until it does, so the final matrix avoids bias from removing elements.

% Specify size of matrix
dim = 4; 
% Compute probability for sparse matrix based on size of matrix
density = 1 - (1 - 1/(2^(1/dim)))^(1/(dim-1));
% Create sparse matrix
A = full(sprand(dim,dim,density));
% Set diagonal to zeroes
A(eye(size(A)) ~= 0) = 0;

% Check that A satisfied conditions (no row or column with all zeroes)
% If A does not, re-compute A and check again
while ~(all(any(A,1)) && all(any(A,2))) 
    A = full(sprand(dim,dim,density));
    A(eye(size(A)) ~= 0) = 0;
end

When I tested this, it found a valid matrix in a small number of iterations each time.

If you need the matrix to be either sparser or less sparse, you can adjust 'density' to either a different function or a constant to adjust the average number of elements in the matrix.

[Evelyn Salt]

Smart! Thank you, this solves my problem!