Matrices de Hadamard

José A. Alonso

16-04-2020

Las matrices de Hadamard se definen recursivamente como sigue

λ> hadamard 0
( 1 )

λ> hadamard 1
(  1  1 )
(  1 -1 )

λ> hadamard 2
(  1  1  1  1 )
(  1 -1  1 -1 )
(  1  1 -1 -1 )
(  1 -1 -1  1 )

λ> hadamard 3
(  1  1  1  1  1  1  1  1 )
(  1 -1  1 -1  1 -1  1 -1 )
(  1  1 -1 -1  1  1 -1 -1 )
(  1 -1 -1  1  1 -1 -1  1 )
(  1  1  1  1 -1 -1 -1 -1 )
(  1 -1  1 -1 -1  1 -1  1 )
(  1  1 -1 -1 -1 -1  1  1 )
(  1 -1 -1  1 -1  1  1 -1 )

En general, la n-ésima matriz de Hadamard, H(n), es

( H(n-1)  H(n-1) )
( H(n-1) -H(n-1) )

Definir la función

hadamard :: Int -> Matrix Int

tal que (hadamard n) es la n-ésima matriz de Hadamard.

Comprobar con QuickCheck que para todo número natural n, el producto de la n-ésima matriz de Hadamard y su traspuesta es igual al producto de 2^n por la matriz identidad de orden 2^n.

Soluciones

import Data.Matrix (Matrix, identity, joinBlocks, scaleMatrix, transpose)
import Test.QuickCheck

hadamard :: Int -> Matrix Int
hadamard 0 = identity 1
hadamard n = joinBlocks (a, a, a, b)
  where a = hadamard (n-1)
        b = scaleMatrix (-1) a

-- La propiedad es
prop_Hadamard :: (Positive Int) -> Bool
prop_Hadamard (Positive n) =
  h * transpose h == scaleMatrix (2^n) (identity (2^n))
  where h = hadamard n

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_Hadamard
--    +++ OK, passed 100 tests.