Help with Fortran: Generating Random Vectors w/ Binary Values

[sue132]

Hi,

I'm trying to generate a set of random vectors with binary values. I need to generate them such that each time, one new vector gets added to the existing matrix. I have been using call random_number(ranval) for the generation, but I haven't been able to get linearly independent vectors.

(I need to orthogonalize them, so the vectors have to be linearly independent)

Any help would be much appreciated. Any info on random number generators would also be useful.

Thanks,
S.

(P.S. I am currently working with Fortran77)

 

[Mark44]

Hi,

I'm trying to generate a set of random vectors with binary values. I need to generate them such that each time, one new vector gets added to the existing matrix. I have been using call random_number(ranval) for the generation, but I haven't been able to get linearly independent vectors.

You don't provide enough context for me to get very specific, but I'll take a stab at it.

How big are the vectors? And when you say "binary values" I'm assuming you mean the vectors consist of 0s and 1s - just checking.

It might be that you can't do what you're trying to do. Let's say for the sake of simplicity that your vectors have 4 elements, such as <0, 1, 1, 1>. If you generate a vector with four values, that vector and the one you just generated might not form a linearly independent set of vectors. In any case, you'll never get more than 4 vectors for a linearly independent set (with n = 4).

The same limitation exists for higher dimension vectors. If n = 25, you won't be able to get more than 25 vectors in your matrix.

Maybe you know all this, but since I don't know your mathematical background, I felt I should mention it.

(I need to orthogonalize them, so the vectors have to be linearly independent)

Any help would be much appreciated. Any info on random number generators would also be useful.

Thanks,
S.

(P.S. I am currently working with Fortran77)

 

[AlephZero]

Your question seems to be about generating Hadamard matrices, or a generalization of them. http://en.wikipedia.org/wiki/Hadamard_matrix

 

[sue132]

Your question seems to be about generating Hadamard matrices, or a generalization of them. http://en.wikipedia.org/wiki/Hadamard_matrix

I think that is what my end result would be. I have to generate a matrix with random vectors, and then when i do the orthogonalization, I think I'll get a Hadamard matrix as the result.
Thanks for the info

 

[sue132]

You don't provide enough context for me to get very specific, but I'll take a stab at it.

How big are the vectors? And when you say "binary values" I'm assuming you mean the vectors consist of 0s and 1s - just checking.

It might be that you can't do what you're trying to do. Let's say for the sake of simplicity that your vectors have 4 elements, such as <0, 1, 1, 1>. If you generate a vector with four values, that vector and the one you just generated might not form a linearly independent set of vectors. In any case, you'll never get more than 4 vectors for a linearly independent set (with n = 4).

The same limitation exists for higher dimension vectors. If n = 25, you won't be able to get more than 25 vectors in your matrix.

Maybe you know all this, but since I don't know your mathematical background, I felt I should mention it.

So, if I have 10 as my vector length, I should be able to get at least 9 linearly independent vectors, right? I'm currently using +1's and -1's as my binary values.

What I'm doing at present is adding one vector at a time to my existing matrix using a random number generator (my random numbers are between 0 and 1, so I made anything lesser than 0.5 a -1, and the rest are +1's.) Should I change my random number generator, or would it be a better idea to ignore a dependent vector and generate a new vector in its place?

Thanks for the reply

 

[Mark44]

Why do you have -1 entries in your vectors? There's nothing wrong with it, but when most people think binary, they think 0 and 1. Having a 0 instead of a -1 might make the calculations easier.

If your vectors are length 10, you should be able to come up with 10 lin. independent vectors.

What I would do is generate a vector, and then figure out if that vector and the ones I already had form a linearly independent set.

I don't know any good algorithms for that, but at each step (with N vectors, where 2 <= N <= 10), you need to solve N equations for N unknowns. If the only solution is c₁ = c₂ = ... = c_N = 0, then the vectors are linearly independent.

If the vector I just came up with turned out to be a linear combination of the others (hence the set of vectors is now linearly dependent) I would discard it, and try again.

 

[sue132]

Why do you have -1 entries in your vectors? There's nothing wrong with it, but when most people think binary, they think 0 and 1. Having a 0 instead of a -1 might make the calculations easier.

I'm using -1's as they are more convenient than zeros for my further calculations.

What I would do is generate a vector, and then figure out if that vector and the ones I already had form a linearly independent set.

I have been trying to do that. As I generate each vector, I'm checking its projection with the previous vectors. If it's in the same direction as any of those, then I get a projection value of 0, and hence it will be linearly dependent. Hope I'm right in doing it this way.

If the vector I just came up with turned out to be a linear combination of the others (hence the set of vectors is now linearly dependent) I would discard it, and try again.

This is what I'm trying to do now.

Thanks again for your patience.

(P.S. I'm still fairly new to Fortran, so am having some trouble finding my way around)

 

[sue132]

I figured it out. Thanks