Math::MatrixBool - Matrix of Booleans

NAME
SUPPORTED PLATFORMS
SYNOPSIS
DESCRIPTION
OVERLOADED OPERATORS
SEE ALSO
VERSION
AUTHOR
COPYRIGHT
LICENSE AGREEMENT

NAME

Math::MatrixBool - Matrix of Booleans

Easy manipulation of matrices of booleans (Boolean Algebra)

SUPPORTED PLATFORMS

Linux
Solaris
Windows

This module is not included with the standard ActivePerl distribution. It is available as a separate download using PPM.

SYNOPSIS

use Math::MatrixBool;
$new_matrix = new Math::MatrixBool($rows,$columns);
the matrix object constructor method

An exception is raised if the necessary memory cannot be allocated.
$new_matrix = Math::MatrixBool->new($rows,$columns);
alternate way of calling the matrix object constructor method
$new_matrix = $some_matrix->new($rows,$columns);
still another way of calling the matrix object constructor method ($some_matrix is not affected by this)

$new_matrix = Math::MatrixBool->new_from_string($string);

This method allows you to read in a matrix from a string (for instance, from the keyboard, from a file or from your code).

The syntax is simple: each row must start with ``[ '' and end with `` ]\n'' (``\n'' being the newline character and `` '' a space or tab) and contain one or more numbers, all separated from each other by spaces or tabs.

Additional spaces or tabs can be added at will, but no comments.

Numbers are either ``0'' or ``1''.

Examples:

    $string = "[ 1 0 0 ]\n[ 1 1 0 ]\n[ 1 1 1 ]\n";
    $matrix = Math::MatrixBool->new_from_string($string);
    print "$matrix";

By the way, this prints

    [ 1 0 0 ]
    [ 1 1 0 ]
    [ 1 1 1 ]

But you can also do this in a much more comfortable way using the shell-like ``here-document'' syntax:

    $matrix = Math::MatrixBool->new_from_string(<<'MATRIX');
    [  1  0  0  0  0  0  1  ]
    [  0  1  0  0  0  0  0  ]
    [  0  0  1  0  0  0  0  ]
    [  0  0  0  1  0  0  0  ]
    [  0  0  0  0  1  0  0  ]
    [  0  0  0  0  0  1  0  ]
    [  1  0  0  0  0  0  1  ]
    MATRIX

You can even use variables in the matrix:

    $c1  =  $A1 * $x1 - $b1 >= 0  ?"1":"0";
    $c1  =  $A2 * $x2 - $b2 >= 0  ?"1":"0";
    $c1  =  $A3 * $x3 - $b3 >= 0  ?"1":"0";

    $matrix = Math::MatrixBool->new_from_string(<<"MATRIX");

        [   1    0    0   ]
        [   0    1    0   ]
        [  $c1  $c2  $c3  ]

    MATRIX

(Remember that you may use spaces and tabs to format the matrix to your taste)

Note that this method uses exactly the same representation for a matrix as the ``stringify'' operator ``'': this means that you can convert any matrix into a string with $string = "$matrix"; and read it back in later (for instance from a file!).

If the string you supply (or someone else supplies) does not obey the syntax mentioned above, an exception is raised, which can be caught by ``eval'' as follows:

    print "Please enter your matrix (in one line): ";
    $string = <STDIN>;
    $string =~ s/\\n/\n/g;
    eval { $matrix = Math::MatrixBool->new_from_string($string); };
    if ($@)
    {
        print "$@";
        # ...
        # (error handling)
    }
    else
    {
        # continue...
    }

or as follows:

    eval { $matrix = Math::MatrixBool->new_from_string(<<"MATRIX"); };
    [   1    0    0   ]
    [   0    1    0   ]
    [  $c1  $c2  $c3  ]
    MATRIX
    if ($@)
    # ...

Actually, the method shown above for reading a matrix from the keyboard is a little awkward, since you have to enter a lot of ``\n'''s for the newlines.

A better way is shown in this piece of code:

  while (1)
  {
      print "\nPlease enter your matrix ";
      print "(multiple lines, <ctrl-D> = done):\n";
      eval { $new_matrix =
          Math::MatrixBool->new_from_string(join('',<STDIN>)); };
      if ($@)
      {
          $@ =~ s/\s+at\b.*?$//;
          print "${@}Please try again.\n";
      }
      else { last; }
  }

Possible error messages of the ``new_from_string()'' method are:

    Math::MatrixBool::new_from_string(): syntax error in input string
    Math::MatrixBool::new_from_string(): empty input string

If the input string has rows with varying numbers of columns, the following warning will be printed to STDERR:

    Math::MatrixBool::new_from_string(): missing elements will be set to zero!

If everything is okay, the method returns an object reference to the (newly allocated) matrix containing the elements you specified.

($rows,$columns) = $matrix->Dim();
returns the dimensions (= number of rows and columns) of the given matrix
$matrix->Empty();
sets all elements in the matrix to ``0''
$matrix->Fill();
sets all elements in the matrix to ``1''
$matrix->Flip();
flips (i.e., complements) all elements in the given matrix
$matrix->Zero();
sets all elements in the matrix to ``0''
$matrix->One();
fills the matrix with one's in the main diagonal and zero's elsewhere

Note that multiplying this matrix with itself yields the same matrix again (provided it is a square matrix)!
$matrix->Bit_On($row,$column);
sets a given element to ``1''
$matrix->Insert($row,$column);
alias for ``Bit_On()'', deprecated
$matrix->Bit_Off($row,$column);
sets a given element to ``0''
$matrix->Delete($row,$column);
alias for ``Bit_Off()'', deprecated
$boolean = $matrix->bit_flip($row,$column);
flips (i.e., complements) a given element and returns its new value
$boolean = $matrix->flip($row,$column);
alias for ``bit_flip()'', deprecated
$boolean = $matrix->bit_test($row,$column);
tests wether a given element is set
$boolean = $matrix->contains($row,$column);
tests wether a given element is set (alias for ``bit_test()'')
$boolean = $matrix->in($row,$column);
alias for ``bit_test()'', deprecated
$elements = $matrix->Number_of_elements();
calculates the number of elements contained in the given matrix
$norm_max = $matrix->Norm_max();
calculates the ``maximum''-norm of the given matrix
$norm_one = $matrix->Norm_one();
calculates the ``1''-norm of the given matrix
$matrix1->Addition($matrix2,$matrix3);
calculates the sum of matrix2 and matrix3 and stores the result in matrix1 (in-place is also possible)
$product_matrix = $matrix1->Multiplication($matrix2);
calculates the product of matrix1 and matrix2 and returns an object reference to a new matrix where the result is stored; uses ``^'' as boolean addition operator internally
$product_matrix = $matrix1->Product($matrix2);
calculates the product of matrix1 and matrix2 and returns an object reference to a new matrix where the result is stored; uses ``|'' as boolean addition operator internally
$closure = $matrix->Kleene();
computes the reflexive transitive closure of the given matrix and returns a new matrix containing the result. (The original matrix is not changed by this in any way!)

Uses a variant of Kleene's algorithm. See the Math::Kleene(3) manpage for more details about this algorithm!

This algorithm is mainly used in graph theory: Each position in the matrix corresponds to a (directed!) possible connection (``edge'') between two points (``vortices'') of a graph. Each position in the matrix contains a ``1'' if the corresponding edge is part of the graph and a ``0'' if not.

Computing the closure of this matrix means to find out if there is a path from any vortice of the graph to any other (a path consisting of one or more edges).

Note that there are more applications of Kleene's algorithm in other fields as well (see also Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3)).
$matrix1->Union($matrix2,$matrix3);
calculates the union of matrix2 and matrix3 and stores the result in matrix1 (in-place is also possible)
$matrix1->Intersection($matrix2,$matrix3);
calculates the intersection of matrix2 and matrix3 and stores the result in matrix1 (in-place is also possible)
$matrix1->Difference($matrix2,$matrix3);
calculates matrix2 ``minus'' matrix3 ( = matrix2 \ matrix3 ) and stores the result in matrix1 (in-place is also possible)

Note that this is set difference, not matrix difference! Matrix difference degenerates to (= is the same as) matrix addition in a Boolean Algebra!!
$matrix1->ExclusiveOr($matrix2,$matrix3);
calculates the exclusive-or (which in the case of a Boolean Algebra happens to be the same as the addition) of matrix2 and matrix3 and stores the result in matrix1 (in-place is also possible)
$matrix1->Complement($matrix2);
calculates the complement of matrix2 and stores the result in matrix1 (in-place is also possible)
$matrix1->Transpose($matrix2);
calculates the transpose of matrix2 and stores the result in matrix1 (in-place is also possible if and only if the matrix is a square matrix!); in general, matrix1 must have reversed numbers of rows and columns in relation to matrix2
$boolean = $matrix1->equal($matrix2);
tests if matrix1 is the same as matrix2
$boolean = $matrix1->subset($matrix2);
tests if matrix1 is a subset of matrix2
$boolean = $matrix1->inclusion($matrix2);
alias for ``subset()'', deprecated
$boolean = $matrix1->lexorder($matrix2);
tests if matrix1 comes lexically before matrix2, i.e., if (matrix1 <= matrix2) holds, as though the two bit vectors used to represent the two matrices were two large numbers in binary representation

(Note that this is an arbitrary order relationship!)
$result = $matrix1->Compare($matrix2);
lexically compares matrix1 and matrix2 and returns -1, 0 or 1 if (matrix1 < matrix2), (matrix1 == matrix2) or (matrix1 > matrix2) holds, respectively

(Again, the two bit vectors representing the two matrices are compared as though they were two large numbers in binary representation)
$matrix1->Copy($matrix2);
copies the contents of matrix2 to an ALREADY EXISTING matrix1
$new_matrix = $some_matrix->Shadow();
returns an object reference to a NEW but EMPTY matrix of the SAME SIZE as some_matrix
$twin_matrix = $some_matrix->Clone();
returns an object reference to a NEW matrix of the SAME SIZE as some_matrix; the contents of some_matrix have ALREADY BEEN COPIED to the new matrix
Hint: method names all in lower case indicate a boolean return value!
(Except for ``new()'' and ``new_from_string()'', of course!)

Please refer to OVERLOADED OPERATORS below for ways of using overloaded operators instead of explicit method calls in order to facilitate calculations with matrices!

DESCRIPTION

This class lets you dynamically create boolean matrices of arbitrary size and perform all the basic operations for matrices on them, like

-

setting or deleting elements,

-

testing wether a certain element is set,

-

computing the sum, difference, product, closure and complement of matrices,

(you can also compute the union, intersection, difference and exclusive-or of the underlying bit vector)

-

copying matrices,

-

testing two matrices for equality or inclusion (subset relationship), and

-

computing the number of elements and the norm of a matrix.

Please refer to OVERLOADED OPERATORS below for ways of using overloaded operators instead of explicit method calls in order to facilitate calculations with matrices!

OVERLOADED OPERATORS

Calculations with matrices can not only be performed with explicit method calls using this module, but also through ``magical'' overloaded arithmetic and relational operators.

For instance, instead of writing

    $matrix1 = Math::MatrixBool->new($rows,$columns);
    $matrix2 = Math::MatrixBool->new($rows,$columns);
    $matrix3 = Math::MatrixBool->new($rows,$columns);

    [...]

    $matrix3->Multiplication($matrix1,$matrix2);

you can just say

    $matrix1 = Math::MatrixBool->new($rows,$columns);
    $matrix2 = Math::MatrixBool->new($rows,$columns);

    [...]

    $matrix3 = $matrix1 * $matrix2;

That's all!

Here is the list of all ``magical'' overloaded operators and their semantics (meaning):

Unary operators: '-', '~', 'abs', testing, '!', '``'''

Binary (arithmetic) operators: '+', '*', '|', '-', '&', '^'

Binary (relational) operators: '==', '!=', '<', '<=', '>', '>='

Binary (relational) operators: 'cmp', 'eq', 'ne', 'lt', 'le', 'gt', 'ge'

Note that both arguments to a binary operator from the list above must be matrices; numbers or other types of data are not permitted as arguments and will produce an error message.

'-'

Unary Minus / Complement ( $matrix2 = -$matrix1; )

The unary operator '-' computes the complement of the given matrix.

'~'

Transpose ( $matrix2 = ~$matrix1; )

The operator '~' computes the transpose of the given matrix.

abs

Absolute Value ( $no_of_elem = abs($matrix); )

Here, the absolute value of a matrix has been defined as the number of elements the given matrix contains. This is NOT the same as the ``norm'' of a matrix!

test

Boolean Test ( if ($matrix) { ... } )

You can actually test a matrix as though it were a boolean value.

No special operator is needed for this; Perl automatically calls the appropriate method in this package if ``$matrix'' is a blessed reference to an object of the ``Math::MatrixBool'' class or one of its derived classes.

This operation returns ``true'' (1) if the given matrix is not empty and ``false'' ('') otherwise.

'!'

Negated Boolean Test ( if (! $matrix) { ... } )

You can also perform a negated test on a matrix as though it were a boolean value. For example:

    if (! $matrix) { ... }

    unless ($matrix) { ... }     #  internally, same as above!

This operation returns ``true'' (1) if the given matrix is empty and ``false'' ('') otherwise.

'``''``'''

``Stringification'' ( print "$matrix"; )

It is possible to get a string representation of a given matrix by just putting the matrix object reference between double quotes.

Note that in general the string representation of a matrix will span over multiple lines (i.e., the string which is generated contains ``\n'' characters, one at the end of each row of the matrix).

Example:

    $matrix = new Math::MatrixBool(5,6);
    $matrix->One();
    print "$matrix";

This will print:

    [ 1 0 0 0 0 0 ]
    [ 0 1 0 0 0 0 ]
    [ 0 0 1 0 0 0 ]
    [ 0 0 0 1 0 0 ]
    [ 0 0 0 0 1 0 ]

'+'

Addition ( $matrix3 = $matrix1 + $matrix2; )

The '+' operator calculates the sum of two matrices.

Examples:

    $all   =  $odd + $even;

    $all  +=  $odd;
    $all  +=  $even;

Note that the '++' operator will produce an error message if applied to an object of this class because adding a number to a matrix makes no sense.

'*'

Multiplication ( $matrix3 = $matrix1 * $matrix2; )

The '*' operator calculates the matrix product of two matrices.

Examples:

    $test   =  $one * $one;

    $test  *=  $one;
    $test  *=  $test;

Note that you can use matrices of any size as long as their numbers of rows and columns correspond in the following way (example):

        $matrix_3 = $matrix_1 * $matrix_2;

                          [ 2 2 ]
                          [ 2 2 ]
                          [ 2 2 ]

              [ 1 1 1 ]   [ 3 3 ]
              [ 1 1 1 ]   [ 3 3 ]
              [ 1 1 1 ]   [ 3 3 ]
              [ 1 1 1 ]   [ 3 3 ]

I.e., the number of columns of matrix #1 is the same as the number of rows of matrix #2, and the number of rows and columns of the resulting matrix #3 is determined by the number of rows of matrix #1 and the number of columns of matrix #2, respectively.

This way you can also perform the multiplication of a matrix with a vector, since a vector is just a degenerated matrix with several rows but only one column, or just one row and several columns.

'|'

Union ( $matrix3 = $matrix1 | $matrix2; )

The '|' operator is used to calculate the union of two matrices (of corresponding elements).

Examples:

    $all   =  $odd | $even;

    $all  |=  $odd;
    $all  |=  $even;

'-'

Difference ( $matrix3 = $matrix1 - $matrix2; )

The operator '-' calculates the (dotted) difference of two matrices, i.e.,

    0 - 0 == 0
    0 - 1 == 0
    1 - 0 == 1
    1 - 1 == 0

for each corresponding element.

Examples:

    $odd   =  $all  - $even;

    $all  -=  $even;

Note that the '--' operator will produce an error message if applied to an object of this class because subtracting a number from a matrix makes no sense.

'&'

Intersection ( $matrix3 = $matrix1 & $matrix2; )

The '&' operator is used to calculate the intersection of two matrices (of the corresponding elements).

Examples:

    $rest  =  $all & $even;

    $all  &=  $even;

'^'

ExclusiveOr ( $matrix3 = $matrix1 ^ $matrix2; )

The '^' operator is used to calculate the exclusive-or of two matrices (of their corresponding elements).

In fact this operation is identical with the addition of two matrices in this case of a Boolean Algebra.

Examples:

    $odd   =  $all  ^ $even;

    $all  ^=  $even;

'=='

Test For Equality ( if ($matrix1 == $matrix2) { ... } )

This operator tests two matrices for equality.

Note that without operator overloading, ( $matrix1 == $matrix2 ) would test wether the two references pointed to the same object! (!)

With operator overloading in effect, ( $matrix1 == $matrix2 ) tests wether the two matrix objects contain exactly the same elements!

'!='

Test For Non-Equality ( if ($matrix1 != $matrix2) { ... } )

This operator tests wether two matrices are different.

Note again that this tests wether the contents of the two matrices are not the same, and not wether the two references are different!

'<'

Test For True Subset ( if ($matrix1 < $matrix2) { ... } )

This operator tests wether $matrix1 is a true subset of $matrix2, i.e. wether the elements contained in $matrix1 are also contained in $matrix2, but not all elements contained in $matrix2 are contained in $matrix1.

Example:

        [ 1 0 0 0 0 ]                       [ 1 0 0 0 1 ]
        [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
        [ 0 0 1 0 0 ]  is a true subset of  [ 0 0 1 0 0 ]
        [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
        [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]

        [ 1 0 0 0 0 ]                       [ 1 0 0 0 1 ]
        [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
   but  [ 0 0 1 0 0 ]   is not a subset of  [ 0 0 1 0 0 ]
        [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
        [ 1 0 0 0 1 ]                       [ 0 0 0 0 1 ]

(nor vice-versa!)

        [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]
        [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
   and  [ 0 0 1 0 0 ]     is a subset of    [ 0 0 1 0 0 ]
        [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
        [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]

but not a true subset because the two matrices are identical.

'<='

Test For Subset ( if ($matrix1 <= $matrix2) { ... } )

This operator tests wether $matrix1 is a subset of $matrix2, i.e. wether all elements contained in $matrix1 are also contained in $matrix2.

This also evaluates to ``true'' when the two matrices are the same.

'>'

Test For True Superset ( if ($matrix1 > $matrix2) { ... } )

This operator tests wether $matrix1 is a true superset of $matrix2, i.e. wether all elements contained in $matrix2 are also contained in $matrix1, but not all elements contained in $matrix1 are contained in $matrix2.

Note that ($matrix1 > $matrix2) is exactly the same as ($matrix2 < $matrix1).

'>='

Test For Superset ( if ($matrix1 >= $matrix2) { ... } )

This operator tests wether $matrix1 is a superset of $matrix2, i.e. wether all elements contained in $matrix2 are also contained in $matrix1.

This also evaluates to ``true'' when the two matrices are equal.

Note that ($matrix1 >= $matrix2) is exactly the same as ($matrix2 <= $matrix1).

cmp

Compare ( $result = $matrix1 cmp $matrix2; )

This operator compares the two matrices lexically, i.e. it regards the two bit vectors representing the two matrices as two large (unsigned) numbers in binary representation and returns ``-1'' if the number for $matrix1 is smaller than that for $matrix2, ``0'' if the two numbers are the same (i.e., when the two matrices are equal!) or ``1'' if the number representing $matrix1 is larger than the number representing $matrix2.

Note that this comparison has nothing to do whatsoever with algebra, it is just an arbitrary order relationship!

It is only intended to provide an (arbitrary) order by which (for example) an array of matrices can be sorted, for instance to find out quickly (using binary search) if a specific matrix has already been produced before in some matrix-producing process or not.

eq