# 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 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,...)?

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
Shlomo Geva on 8 Mar 2021
Nice Matt. Thank you.

Steven Lord on 8 Mar 2021
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.
Elapsed time is 0.305544 seconds.

Walter Roberson on 31 Jan 2018
(dec2bin(0:(2^(N-1)-1),N)-'0') * 2 - 1
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.