How to generate a set of N mutually orthogonal (N being a power of 2) N-dimensional binary vectors [+1,-1]?

17 views (last 30 days)
Shlomo Geva
Shlomo Geva on 31 Jan 2018
Commented: Shlomo Geva on 8 Mar 2021
For instance:
with N=2 we could have [1 1; 1 -1]
with N=4, we could have [1 1 1 1; 1 1 -1 -1; 1 -1 1 -1; 1 -1 -1 1]
How to efficiently generate N mutually orthogonal binary vectors for larger N (8,16,32,64,...,4096,...)?

Accepted Answer

Matt J
Matt J on 8 Mar 2021
Edited: Matt J on 8 Mar 2021
N=4096;
[C,C0]=deal([1 1;1 -1]);
tic;
for i=1:log2(N/2)
C=kron(C0,C);
end
toc
Elapsed time is 0.079038 seconds.
isOrthogonal=isequal(C*C.', N*speye(N))
isOrthogonal = logical
1
C
C = 4096×4096
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1

More Answers (2)

Steven Lord
Steven Lord on 8 Mar 2021
See the hadamard function.
  1 Comment
Matt J
Matt J on 8 Mar 2021
For some reason, I find this a fair bit slower than the kron-based solution
N=4096;
tic;
[C,C0]=deal([1 1;1 -1]);
for i=1:log2(N/2)
C=kron(C0,C);
end
toc
Elapsed time is 0.075004 seconds.
tic; hadamard(N); toc
Elapsed time is 0.305544 seconds.

Sign in to comment.


Walter Roberson
Walter Roberson on 31 Jan 2018
(dec2bin(0:(2^(N-1)-1),N)-'0') * 2 - 1
  9 Comments
Shlomo Geva
Shlomo Geva on 8 Mar 2021
On the machine I use we can go up to 131072 x 131072 x 8 bytes (using 2^9 and 2^8 in code above). It takes 10 seconds. We have 1.5TB of RAM. After that we are toast, but that is all we need so this is great.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by