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)
{
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 (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 (inputStr.IndexOf(" ") == -1 && parts.Length == 2)
{
SetNumeratorDenominatorAndTheirSigns(Int32.Parse(parts[0]), Int32.Parse(parts[1]));
FloatingNumber = GetQuotient(Numerator, Denominator);
return;
}
if (parts.Length == 3)
{
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 (!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()
{
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
- ...