programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Bear Bibeault
• Knute Snortum
• Liutauras Vilda
Sheriffs:
• Tim Cooke
• Devaka Cooray
• Paul Clapham
Saloon Keepers:
• Tim Moores
• Frits Walraven
• Ron McLeod
• Ganesh Patekar
• salvin francis
Bartenders:
• Tim Holloway
• Carey Brown
• Stephan van Hulst

Need help in generating Hadamard Matrix

Ranch Hand
Posts: 106
2
Hi, everyone

Recently I came across this problem in the book "Introduction to Programming in JAVA An Interdisciplinary Approach" under creative examples. I know the properties of Hadamard matrix. Like, they are all square matrices. H(1) consists of a single row and column with the value T. And in general if we have H(N) then we can create H(2N) by defining the matrix as 1st row [H(N)  H(N)] and second row [H(N)  -H(N)]. So whenever an user enters a the value for N, I assume it to be a power of 2. and declare a NXN matrix, whose first element H[0][0] is true. But then how do I populate the array from that point. I need help in understanding the approach to this program.
For reference here is the complete question,

Hadamard matrix. The N-by-N Hadamard matrix H(N) is a boolean matrix with the remarkable property that any two rows differ in exactly N/2 entries. (This property makes it useful for designing error-correcting codes.) H(1) is a 1-by-1 matrix with the single entry true, and for N>1, H(2N) is obtained by aligning four copies of H(N) in a large square, and then inverting all of the entries in the lower right N-by-N copy, as shown in the following examples (with T representing true and F representing false, as usual).

Write a program that takes one command-line argument N and prints H(N). Assume that N is a power of 2.

Regards,
Ranajoy

Master Rancher
Posts: 3036
106
• 1
Having an H(N), first thing is to create a H(2N). Then, if you look at the Arrays class, you will see some very handy methods there, relating to filling and copying.
A method that 'inverts' a boolean matrix also comes in handy.

Marshal
Posts: 62231
193
Have added code tags to your matrices, using the Text option in the dropdown list. I think it makes it look better, but the widths of the characters are irregular, so I had to remove some spaces.

I think you shou‍ld explain the algorithm behind creating the matrix. Once you have the algorithm written out in a nice simple form it shoul‍ld be easy to convert to code.
By the way: Have you considered changing each row to a number? Regard a T as the bit set (=1) and a false a a 0. That way you can change each row to an int or long depending on its size. Does that help at all?

Ranajoy Saha
Ranch Hand
Posts: 106
2
Following Piet Souris suggestion, what I did was created an H(2) matrix and wrote a code to fill any square matrix with the values of H(2). Then, what I did was to invert the outputs as soon as the last matrix is to be inserted.
Basically the code goes as follows.

This is the display() method.

This code has some problem. Here are some of the outputs.

Everything goes all right till 4. but when I enter 8, the code ends up giving me this.

How should I correct this issue? Where am I going wrong?

Ranajoy Saha
Ranch Hand
Posts: 106
2
The logic that I went with in writing the above code will run fine, if I have the Hadamard Matrix(N/2) before hand, where N is the size of the Hadamard matrix the user wants.

Ranajoy Saha
Ranch Hand
Posts: 106
2
This is another approach I took at solving the problem. But still this code fails for any N, greater than 8.

I'm out of ideas, please someone help me out here.

Sheriff
Posts: 12815
211
I would try to use some recursion. To get H(8), fill first three quadrants with H(4), then invert H(4) to get the fourth quadrant. Recursively, to get H(4), you'd fill first three quadrants with H(2), then invert H(2) to get the fourth quadrant. To get H(2), ...

Campbell Ritchie
Marshal
Posts: 62231
193

Junilu Lacar wrote:. . . To get H(8), . . . to get H(4), . . . To get H(2), ...

That is exactly what you are looking for. An algorithm written out nice and simply, so you can implement it. Of course the algorithm starts with the magic word recursion. Recursion isn't quite witchcraft, but if you want a happy life, don't try to work out how recursion works. Just trust that it does work

Ranch Hand
Posts: 1159
9

Junilu Lacar wrote:I would try to use some recursion. To get H(8), fill first three quadrants with H(4), then invert H(4) to get the fourth quadrant. Recursively, to get H(4), you'd fill first three quadrants with H(2), then invert H(2) to get the fourth quadrant. To get H(2), ...

Orrr....

You could write write a recursive method to return just a single boolean.  Conveniently, H(N)[X, Y] is the same for all N where X and Y are reasonable (i.e. X,Y < N)

Disclaimer: This is toally untested code.

Now just fill in any size array you want.

Ryan McGuire
Ranch Hand
Posts: 1159
9
Orrr...

Is there a way to calculate a given array value from just the indexes?  For instance, without working the entire H(128) matrix out, I would bet that H(128)[42, 95] is T.  Can anyone confirm or refute that?

Ryan McGuire
Ranch Hand
Posts: 1159
9

Ryan McGuire wrote:Orrr... Is there a way to calculate a given array value from just the indexes?  For instance, without working the entire H(128) matrix out, I would bet that H(128)[42, 95] is T.  Can anyone confirm or refute that?

Clarification:  I mean is there a non-recursive way to calculate a given array value.

Campbell Ritchie
Marshal
Posts: 62231
193
There probably is. You will have to search for algorithms.

Ryan McGuire
Ranch Hand
Posts: 1159
9

Campbell Ritchie wrote:There probably is. You will have to search for algorithms.

Search for?  Figure the algorithm out your own darn self.  It's just a bunch of Ts and Fs in a fairly regular pattern.  How hard can it be?

Ryan McGuire
Ranch Hand
Posts: 1159
9

Ryan McGuire wrote:

Campbell Ritchie wrote:There probably is. You will have to search for algorithms.

Search for?  Figure the algorithm out your own darn self.  It's just a bunch of Ts and Fs in a fairly regular pattern.  How hard can it be?

I think this thread could be moved over to Programming Diversions.  It's easy enough that it should be gettable, but it's hard enough to support multiple plans of attack AND provide some nice aha moments along the way.  Could some kind Sheriff move this there if you agree?

Campbell Ritchie
Marshal
Posts: 62231
193
It has gone all quiet, but I shall take the hint and move it to Diversions.

Ryan McGuire
Ranch Hand
Posts: 1159
9
Since I think I've come up with the best way to calculate the values in a Hadamard matrix, I'll pose the question:

Given the definition of Hadamard matrices in the OP, what's the best (easy to program, low memory reqs, fast to execute, etc) way to...
1. Determine a single value without necessarily calculating the entire matrix?  e.g. What is H512[344][285]?
2. Print out the entire matrix.

Is the answer to part 2 just answering part 1 over and over?

Piet Souris
Master Rancher
Posts: 3036
106
I remember that a recursive solution was very easy and elegant, and that I next tried to devise a non-recursive formula that, given x and y coordinates, directly lead to either H1 or !H1. (and H1 is the given starting situation). But that turned out to be so complex that I soon gave up. It's much more difficult than coming up with a formula for say the Fibonacci series, with only n as variable. I even tried to prove some full induction formula, but in vain.

If you have such a direct formula, then I would love to see it.

Ryan McGuire
Ranch Hand
Posts: 1159
9

Piet Souris wrote:If you have such a direct formula, then I would love to see it.

Rather than give out (what I think is) the answer, let me ask...
1. For a given H(n), there are four copies of H(n/2).  Where is H(n/2) used as-is and where is it inverted (i.e. XORed)?  More secifically, is there a way to characterize where the copy of H(n/2) is inverted from just the indexes?  (Something like, "if x and y are both prime numbers, invert H(n/2).")

2. Once you answer that for H(n) and H(n/2), how does that relate to H(n/2) and  H(n/4), etc.

3. Is there an easy way to describe how many times H(1)[0][0] gets XORed to arrive at all the other values?

Piet Souris
Master Rancher
Posts: 3036
106
Anyone who has a recursive solution knows this reasoning. That''s not the problem. I am looking for a non recursive formula without any ifs and whiles, just a plain simple formula like:

H512(345, 261) =( 512 ^([261 / n!] (floor function) % 2 == 0) && H1(1,1)

Do you have such a function? I do not need to know it, but if you do I'll have another try.

Ryan McGuire
Ranch Hand
Posts: 1159
9

Piet Souris wrote:Anyone who has a recursive solution knows this reasoning. That''s not the problem. I am looking for a non recursive formula without any ifs and whiles, just a plain simple formula like:

H512(345, 261) =( 512 ^([261 / n!] (floor function) % 2 == 0) && H1(1,1)

Do you have such a function? I do not need to know it, but if you do I'll have another try.

Yes, I do.  It cheats just a little in that it's not 100% O(1).  However, the source code is nice and short because it uses a method in one of the standard Java classes.

Piet Souris
Master Rancher
Posts: 3036
106
hi Ryan,

yes, it is indeed very simple and almost O(1). Also in H(n, x, y, startBoolean) it is remarkable that the value does not depend on n, the order of the Hadamard. And I used a method from a standard class too. Now, what is the chance that we have the same? Shall I send you a PM?

Ryan McGuire
Ranch Hand
Posts: 1159
9
Feel free.  I suspect we have pretty much the same answer.  By the way, if you use that built-in function, I guess it does turn out to be O(1) as long n <= 2^32.

Piet Souris
Master Rancher
Posts: 3036
106
Thanks for the inspiration, and what a lovely formula. Have a cow, truly deserved!

Piet Souris
Master Rancher
Posts: 3036
106
The recent topic from Ranajoy Saha brought this old topic to mind. The formula that Ryan and I came up with, for anyone interested (and I hope that Ryan has no objection):

 If you settle for what they are giving you, you deserve what you get. Fight for this tiny ad! RavenDB is an Open Source NoSQL Database that’s fully transactional (ACID) across your database https://coderanch.com/t/704633/RavenDB-Open-Source-NoSQL-Database