Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Need help in generating Hadamard Matrix  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Piet Souris
Rancher
Posts: 1980
67
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 55717
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 55717
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Ryan McGuire
Ranch Hand
Posts: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 55717
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There probably is. You will have to search for algorithms.
 
Ryan McGuire
Ranch Hand
Posts: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 55717
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It has gone all quiet, but I shall take the hint and move it to Diversions.
 
Ryan McGuire
Ranch Hand
Posts: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1980
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1980
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1980
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1142
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1980
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the inspiration, and what a lovely formula. Have a cow, truly deserved!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!