Click here to Skip to main content
Click here to Skip to main content

Tagged as

Solving Basic Matrix Operations

, 24 Mar 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
Using custom FractionalNumber and Matrix classes.

Introduction  

Because solving matrices' problems in linear algebra is error-prone, I need a tool to verify my calculation results. Requirements for such a tool include basic tasks:

  • Checking if a given matrix is (skew) symmetric, lower/upper triangle, etc.
  • Perform scalar multiplication, addition, and multiplication.
  • Get determinant, adjoint, and inverse of a given matrix.
  • And essentially, the results need to preserve (as much as possible) the fractional precise (in the form of rational numbers). This is the main reason I decided to write my own program.

Background

Before continuing, I assume that minimal knowledge of Linear Algebra is needed: basic matrix operations, addition, multiplication, transpose, inverse, etc.

In stead of using floating point primitive data type (double, for example) for elements stored in a matrix, I model a Matrix type with its elements to be a custom type, FractionalNumber.

The Matrix type is defined as:

public class Matrix
{
    private int numberOfRow;
    public int NumberOfRow
    {
        get { return this.numberOfRow; }
        private set { this.numberOfRow = value; }
    }

    private int numberOfColumn;
    public int NumberOfColumn
    {
        get { return this.numberOfColumn; }
        private set { this.numberOfColumn = value; }
    }

    private FractionalNumber[,] elements;
    public FractionalNumber[,] Elements
    {
        get { return this.elements; }
        private set { this.elements = value; }
    }
}

The elements of Matrix are type of FractionalNumber, which is defined as:

public class FractionalNumber
{
    private int numerator;
    public int Numerator
    {
        get { return this.numerator; }
        private set { this.numerator = value; }
    }

    private int denominator;
    public int Denominator
    {
        get { return this.denominator; }
        private set { this.denominator = value; }
    }

    private double floatingNumber;
    public double FloatingNumber
    {
        get { return this.floatingNumber; }
        private set { this.floatingNumber = value; }
    }
}

A FractionalNumber is an abstract data type to model real-world rational numbers. It includes 3 properties: numerator, and denominator (not zero). Both two of them are type Integer. The last property is a floating point number, which is a quotient of numerator and denominator. We can construct a FractionalNumber object by two integers input explicitly (9 and 2, for example), by a string input ("9/4"), or by a double number input (3.1) implicitly (which can convert to a rational number 31/10). Examples of constructors:

public FractionalNumber(double doubleNum)
{
    FloatingNumber = doubleNum;
    Numerator = GetNumeratorAndDenominator(doubleNum)[0];
    Denominator = GetNumeratorAndDenominator(doubleNum)[1];
}

The common idea is to divide a double number, doub = 2.5 for example, into 2 parts: the whole part intPart = 2, and the floating part fPart = 0.5. Then loop i to find the first i that the product of (i * fPart) becomes an int. i = 2 for this example. At this time, we have got numerator = (i * doub), and denominator = i.

* Note: the common way subtracting to get the fPart, then parsing would probably not result the correct values due to the computer number rounding. For example, 4.1 or 9.1 might not result exact 0.1 for fPart. So, this program tracks the fPart by the dot "." sign.

private static bool IsInt(double number)
{
    return (number % 1 == 0);
}

private static int[] GetNumeratorAndDenominator(double doubNum)
{

    int[] parts = new int[2];
    String doubNumStr = doubNum.ToString("0.0");
    String[] nums = doubNumStr.Split(new String[] { "." }, StringSplitOptions.None);
    int iPart = Int32.Parse(nums[0]);
    double fPart = Double.Parse("." + nums[1]);

    int numeratorPart = 1;
    int denominatorPart = 1;

    if (fPart == 0.0)
    {
        numeratorPart = iPart;
    }
    else if (fPart != 0.0)
    {
        for (int i = 2; ; i++)
        {
            double t = i * fPart;
            if (IsInt(t))
            {
                denominatorPart = i;
                numeratorPart = (int)(i * doubNum);
                break;
            }
            if (i > 999) // propably irrational number
            {
                throw new Exception("Maybe an irrational number?");
            }
        }
    }

    parts[0] = numeratorPart;
    parts[1] = denominatorPart;
    return parts;
}

For this input string ("3/2", "3\2", or "1 6/4") constructor:

public FractionalNumber(String inputStr)

The method to process it as follow:

private void SetThingsUp(string inputStr)
{
    // If the input string is in the form of a decimal number, such as 1.5
    if (inputStr.IndexOf(".") != -1 || (inputStr.IndexOf(" ") == -1 && 
        inputStr.IndexOf("/") == -1 && inputStr.IndexOf("\\") == -1))
    {
        FloatingNumber = Double.Parse(inputStr);
        Numerator = GetNumeratorAndDenominator(FloatingNumber)[0];
        Denominator = GetNumeratorAndDenominator(FloatingNumber)[1];
        return;
    }

    String[] parts = inputStr.Split(new String[] { " ", "/", "\\" }, StringSplitOptions.RemoveEmptyEntries);

    // If the input string is in the form of 1/2 or 1\2 (= 0.5)
    if (inputStr.IndexOf(" ") == -1 && parts.Length == 2)
    {
        SetNumeratorDenominatorAndTheirSigns(Int32.Parse(parts[0]), Int32.Parse(parts[1]));
        FloatingNumber = GetQuotient(Numerator, Denominator);
        return;
    }

    // If the input string is in the form of 'Mixed Fraction' 1 1/2 (= 1.5)
    if (parts.Length == 3)
    {
        // The whole part is a positive integer
        int wholePart = Int32.Parse(parts[0]);
        SetNumeratorDenominatorAndTheirSigns(Int32.Parse(parts[1]), Int32.Parse(parts[2]));
        FloatingNumber = (double)wholePart + GetQuotient(Numerator, Denominator);
        return;
    }
}

At this time, we have got a basic FractionalNumber (a/b) set up. Because matrices' operations are on their elements (FractionalNumber object), these operations are multiplication, addition, and comparison, so we need to overload the corresponding these operators (+, -, *, /, ==, !=). For example:

public static FractionalNumber operator *(FractionalNumber a, FractionalNumber b)
{
    int num = a.Numerator * b.Numerator;
    int den = a.Denominator * b.Denominator;
    return new FractionalNumber(num, den);
}

Things left to do for FractionalNumber class are to set the appropriate sign (when both numerator and denominator are negative, for example), override ToString(), and simplify the rational number. For example:

private void Simplify()
{
    int gcd = MatLib.General.GetGcd(Math.Abs(Numerator), Math.Abs(Denominator));
    Numerator = Numerator / gcd;
    Denominator = Denominator / gcd;
}

Where GetGcd() is the method to get the greatest common divisor.

Now, come back the the Matrix type. There are two ways to construct a matrix object:

public Matrix(int m, int n)
{
    NumberOfRow = m;
    NumberOfColumn = n;
    Elements = new FractionalNumber[m, n];
}

And:

public Matrix(FractionalNumber[,] matrix)
{
    NumberOfRow = matrix.GetUpperBound(0) + 1;
    NumberOfColumn = matrix.GetUpperBound(1) + 1;
    Elements = new FractionalNumber[NumberOfRow, NumberOfColumn];
    for (int i = 0; i < NumberOfRow; i++)
        for (int j = 0; j < NumberOfColumn; j++)
            Elements[i, j] = matrix[i, j];
}

After initializing a matrix object, we need a variety of methods to check if it is square, zero, diagonal, identity, symmetric, skew, lower, or upper triangle matrix. For example:

public bool IsSkewSymmetricMatrix() // if Transpose(A) = -A
{
    if (!IsSquareMatrix())
    {
        return false;
    }
    Matrix tranMatrix = this.GetTranspose();
    FractionalNumber negativeOne = new FractionalNumber(-1);
    if (tranMatrix == negativeOne * this)
    {
        return true;
    }
    else
    {
        return false;
    }
}

Of course, we need to overload operators to be able to perform calculations, such as matrix C = a * A, with a is a rational number. Example:

public static Matrix operator *(FractionalNumber fNumber, Matrix A)
{
    Matrix B = new Matrix(A.NumberOfRow, A.NumberOfColumn);
    for (int i = 0; i < A.NumberOfRow; i++)
        for (int j = 0; j < A.NumberOfColumn; j++)
            B.Elements[i, j] = A.Elements[i, j] * fNumber;
    return B;
}

Or C = A + B

public static Matrix operator +(Matrix A, Matrix B)
{
    if (A.NumberOfRow != B.NumberOfRow || A.NumberOfColumn != B.NumberOfColumn)
    {
        throw new Exception("ERROR: Incompatible sizes of the two matrices!");
    }
    Matrix C = new Matrix(A.NumberOfRow, A.NumberOfColumn);
    for (int i = 0; i < A.NumberOfRow; i++)
        for (int j = 0; j < A.NumberOfColumn; j++)
            C.Elements[i, j] = A.Elements[i, j] + B.Elements[i, j];
    return C;
}

The last and hardest part, probably is to implement procedures to get sub-matrix, adjoint, and inverse of a given matrix A. But searching Google and CodeProject will give many useful hints. Examples:

public FractionalNumber GetDeterminant()
{
    if (!this.IsSquareMatrix())
    {
        throw new Exception("ERROR: Need to be a square matrix.");
    }
    if (Elements.Length == 1)
    {
        return GetElementAt(0, 0);
    }
    if (Elements.Length == 4)
    {
        return (GetElementAt(0, 0) * GetElementAt(1, 1) - GetElementAt(0, 1) * GetElementAt(1, 0));
    }
    FractionalNumber fNum = new FractionalNumber(0.0);
    for (int i = 0; i < NumberOfColumn; i++)
    {
        fNum += (new FractionalNumber(sign(i))) * GetElementAt(0, i) * this.GetSubMatrix(0, i).GetDeterminant();
    }
    return fNum;
}

In the determinant (det) method above, the index of GetElementAt() and GetSubMatrix() is based zero. The sign() will result 1 if i is even. In order to get the inverse, we need to find the adjoint matrix, adj(A):

public Matrix GetAdjoint()
{
    Matrix coMatrix = new Matrix(NumberOfRow, NumberOfColumn);
    for (int i = 0; i < NumberOfRow; i++)
    {
        for (int j = 0; j < NumberOfColumn; j++)
        {
            coMatrix.Elements[i, j] = new FractionalNumber(sign(i)) * 
              new FractionalNumber(sign(j)) * this.GetSubMatrix(i, j).GetDeterminant();
        }
    }
    return coMatrix.GetTranspose();
}

The formula of inverse of matrix A is: inverse(A) = [1/det(A)] * adj(A).

public Matrix GetInverse()
{
    // inverse(A) = (1/det(A)) * adj(A)
    Matrix iMatrix = iMatrix = ((new FractionalNumber(1)) / GetDeterminant()) * GetAdjoint();
    return iMatrix;
}

The Code

Although I have spent a lot of time for this project, but it is worth the effort. This program is useful for me to solve and verify the solutions to the problems in Linear Algebra. I include both the binary execution (Console) for use, and source code for those who are interested.

Credits

The following links are useful references for this program:

History and Plan

  • 03/23/2013: First version release.

Plans:

  • Add more functions, such as solving linear equations.
  • Turn into GUI
  • Translate into Java
  • ...

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Lộc Nguyễn
Software Developer SPAWAR Pacific
United States United States
Currently a senior CS at University of Missouri, St. Louis (UMSL).
I do freelancing in PHP, Web, C# .NET, and Java.
 
Upon graduation in December this year (2014), I will work as a Computer Scientist at SPAWAR San Diego, CA. I am excited about that.
Follow on   Google+

Comments and Discussions

 
SuggestionRow/Columns properties Pinmemberp4koo28-Jan-14 10:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141216.1 | Last Updated 24 Mar 2013
Article Copyright 2013 by Lộc Nguyễn
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid