The program to find the determinant of matrix

Here is the MATLAB program to find the determinant of a nxn matrix by the cofactor method.  I had to develop a separate function for each size of the matrix.  I may be wrong about having to do that – is there a single function that can be written to find the determinant of any nxn matrix using the cofactor method?

The mfile can be downloaded here.   Try the program for a 10×10 matrix – it took about 6 seconds of CPU time on my PC.  A 12×12 matrix determinant would take about 13 minutes of CPU time.  I stopped at a 12×12 matrix.  You can either write a function or generate the function via a program for matrices of 13×13 order and higher.

Contents

Finding the determinant of a matrix using the cofactor method

and comparing the CPU time with MATLAB det function

clc
clear all
format long

% n=Size of matrix
n=6;
% Choosing a matrix of nxn size with random numbers
A=rand(n,n);

% Calculating cputime by cofactor method
tbegin=cputime;
detval=det6(A);
TimeCrammer=cputime-tbegin;

% Calculating cputime by MATLAB det function
tbegin=cputime;
MatlabDet=det(A);
TimeMatlab=vpa(cputime-tbegin,32);

% Printing the times
fprintf('Size of matrix is %gx%g \n',n,n)
fprintf('Determinant by cofactor method = %g \n', detval)
fprintf('Determinant by Matlab function = %g \n', MatlabDet)
fprintf('Approximate CPU time taken by cofactor method = %g seconds\n',TimeCrammer)
fprintf('Approximate CPU time taken by MATLAB function = %e seconds\n',TimeMatlab)

Individual functions for determinant of a nxn matrix

function detvalue=det2(A)
detvalue=A(1,1)*A(2,2)-A(1,2)*A(2,1);
end

function detvalue=det3(A)
n=3;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det2(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det4(A)
n=4;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det3(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det5(A)
n=5;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det4(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det6(A)
n=6;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det5(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det7(A)
n=7;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det6(A(2:n,[1:j-1 j+1:n]));
end
end
function detvalue=det8(A)
n=8;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det7(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det9(A)
n=9;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det8(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det10(A)
n=10;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det9(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det11(A)
n=11;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det10(A(2:n,[1:j-1 j+1:n]));
end
end

function detvalue=det12(A)
n=12;
detvalue=0;
for j=1:1:n
    detvalue=detvalue+(-1)^(j+1)*A(1,j)*det11(A(2:n,[1:j-1 j+1:n]));
end
end
Size of matrix is 6x6 
Determinant by cofactor method = -0.0431 
Determinant by Matlab function = -0.0431 
Approximate CPU time taken by cofactor method = 0.140625 seconds
Approximate CPU time taken by MATLAB function = 1.562500e-02 seconds

The above mfile can be downloaded here.


This post is brought to you by

 

Advertisements

Time it takes to find a determinant

To make the point of how inefficient it is to find the determinant of a matrix by the cofactor method, I wrote a program in MATLAB to demonstrate this.  A google search for a program written in any language to find the determinant by using the cofactor method was not available beyond a 4×4 matrix.  So, I wrote one that finds the determinant of matrices of up to 12×12 order.

I ran the program on an Intel(R) Core(TM) i5-8500 CPU @3.00GHz PC.  Here is a table of the CPU time it took in seconds to find the determinant of a matrix as a function of its order.
______________________________________
Order of matrix               CPU Time to Find
Determinant (s)
______________________________________
6×6                                           0.015625
7×7                                           0.046875
8×8                                           0.203125
9×9                                           0.828125
10×10                                        5.14063
11×11                                       52.6406
12×12                                   623.953
______________________________________

If one continues to do this for a 25×25 matrix, it is estimated that it would take 8.1821198 \times 10^{17} seconds which is more than 25 billion years, and we all know that the estimated age of the universe is less at about 13.77 billion years.

The trend of the approximate time it takes to find the determinant of the next order of the matrix, nxn is approximately n times the time it takes to find the determinant of a (n-1)x(n-1) matrix.  For example, it took a time of 52.6406 seconds for finding the determinant of a 11×11 matrix, while it would be estimated to take approximately 12×52.6406=631.7 seconds for finding the determinant of a 12×12 matrix.  This is close to the 623.953 seconds it actually took.

The above approximate time calculations are in concurrence with the note written by Professor A.J. Wise in 1969, where he showed that the number of arithmetic operations required to evaluate a nxn determinant by cofactor method is given by [n!e]-2, and hence n!e for large n and the time it takes to find the determinant of the next order of the matrix, nxn is approximately n times the time it takes to find the determinant of a (n-1)x(n-1) matrix

Since the arithmetic operation required here are just addition, multiplication and subtraction, the computation time could be crudely estimated as 4Tn!e for large n, where T is the clock cycle time and we assume that an addition or a multiplication or a subtraction each use 4 clock cycle times.  Does it match?

For a 3.00 GHz machine, T={1}/({3 \times 10^9}) seconds to give an approximate time for a 12×12 matrix determinant calculation to be 4 \times {1}/{(3 \times 10^9)} \times 12! e = 1.736  seconds.  It is not even of similar order.  Many items go into calculating CPU time for a numerical algorithm, but to do a comparative analysis, these calculations are quite helpful.


This post is brought to you by

Stripping the tags from an HTML file

Recently, I was moving my webpages created through FrontPage 2003 (please stop snickering -it was a great tool for sites with flat web files) to WordPress.

This required clearing of formatting of the HTML file and one could use http://StripHTML.com for doing so – “StripHTML.com gives you a quick, easy and satisfying way to transform your ugly formatted and/or HTMLified text into a clean and pretty text for you to enjoy.”  However, most of us want to preserve the URL links, titles and the paragraph tags.

This VBA program that can be used within Excel takes an input text file, reads it as a single string, removes all tags except the URLs, paragraphs and titles, and writes to a new text file.

The VBA program below has the input file at “C:\Users\Tranq\Documents\abc\inputhtml.txt”, and outputs to “C:\Users\Tranq\Documents\abc\outputhtml.txt” and you can change these locations in the TextFile_PullData and TextFile_Create functions, respectively.  You can modify the program to read several files in a directory and make it even more efficient.

How to Use: Just open an Excel file. Press Alt+F11, and open a new module. Cut and paste what is given below, or download the text file.  Go to a cell in the excel file and enter =CleanTags(A1) in cell B1.  Make sure you have the input file at C:\Users\Tranq\Documents\abc\inputhtml.txt”.   The location can be modified.

**********************************************

Function CleanTags(HTML As String) As String
‘PURPOSE: Clean HTML tags except the paragraph, weblinks and title
‘ You can comment out if you want these to supress these as well
‘ The instructions are given at the spots.
‘ SOURCE: Unknown and AutarKaw.org
Dim result As String, StripIt As Boolean, c As String, i As Long
HTML = TextFile_PullData()

‘StripIt is used to figure out to include or exclude in output
StripIt = False

‘Looking at each character in the HTML file
For i = 1 To Len(HTML)
‘c is each character
c = Mid(HTML, i, 1)
‘Some conditions to take care for end of input file
If i <= Len(HTML) – 1 Then
‘d is last two characters of file to capture <a and <p
‘Just in case
d = Mid(HTML, i, 2)
Else
d = “”
End If
If i <= Len(HTML) – 3 Then
‘e is last four characters of file to capture </a> and </p>
e = Mid(HTML, i, 4)
Else
e = “”
End If

‘Checking for < character that begins an HTML tag
If c = “<” Then StripIt = True

‘Comment this if you want to strip paragraphs
If d = “<p” Then StripIt = False
If e = “</p>” Then StripIt = False

‘Comment this if you want to strip URL tags and title tags as well.
If d = “<a” Then StripIt = False
If e = “</a>” Then StripIt = False

‘Adds to output or skips it
If StripIt = False Then result = result & c
‘Taking care of closing tag to change the StripIt Boolean
If c = “>” Then StripIt = False
Next i
CleanTags = result

‘Putting the output in a new file
abc = TextFile_Create(result)
‘Run the program by entering =CleanTags(A1) in a blank excel file
‘where you have this module. Puts Done in cell if it runs correctly
CleanTags = “Done”
‘This lets you know the work is done. Comment if you like.
‘MsgBox (“Done”)
End Function

Function TextFile_PullData()
‘PURPOSE: Send All Data From Text File To A String Variable
‘SOURCE: http://www.TheSpreadsheetGuru.com

Dim TextFile As Integer
Dim FilePath As String
Dim FileContent As String

‘File Path of Text File
FilePath = “C:\Users\Tranq\Documents\abc\inputhtml.txt”

‘Determine the next file number available for use by the FileOpen function
TextFile = FreeFile

‘Open the text file
Open FilePath For Input As TextFile

‘Store file content inside a variable
FileContent = Input(LOF(TextFile), TextFile)

‘Report Out Text File Contents
‘MsgBox FileContent

‘Close Text File
Close TextFile
TextFile_PullData = FileContent

End Function

Function TextFile_Create(HTML As String)
‘PURPOSE: Create A New Text File
‘SOURCE: http://www.TheSpreadsheetGuru.com

Dim TextFile As Integer
Dim FilePath As String

‘What is the file path and name for the new text file?
FilePath = “C:\Users\Tranq\Documents\abc\outputhtml.txt”

‘Determine the next file number available for use by the FileOpen function
TextFile = FreeFile

‘Open the text file
Open FilePath For Output As TextFile

‘Write some lines of text
Print #TextFile, HTML

‘Save & Close Text File
Close TextFile

End Function


This post is brought to you by

New site for the Numerical Method MOOC

Our MOOCs on Numerical Methods that were offered on canvas.net site have been moved to a new CANVAS Free for Teachers site.  Current students can continue to use the current MOOCs indefinitely.

For future students, the two-part MOOC now has been combined into one and it is accessible at any time.   There are no deadlines to start or finish.  To enroll, just click this link https://canvas.instructure.com/enroll/KYGTJR and you are on your way to learn Numerical Methods via audiovisual lectures, textbook content and online assessments.


This post is brought to you by

Open Education Resource Repository Links

  • Open education resources (OER) or open course wares (OCW) are everywhere you look.  Many have spent valuable time to make repositories of these courses where one can find links to several courses and these are everywhere as well.  So, when I was answering a recent survey on OERs, they asked users which repositories they had used.  I thought it would be good to have links to all the mentioned repositories, and they are given below.

And if you are wondering what an open education resource is, here is how Open Education Consortium defines it. “An OpenCourseWare (OCW) is a free and open digital publication of high quality college and university‐level educational materials. These materials are organized as courses, and often include course planning materials and evaluation tools as well as thematic content. OpenCourseWare are free and openly licensed, accessible to anyone, anytime via the internet.” Acknowledgement:  I would like to thank USF student Brain G for finding and entering the links.


This post is brought to you by

Maximizing the cross-section of a gutter

This post is brought to you by

Using Watu quizzes and Latex in WordPress

Many years ago, I modified a JavaScript code to develop online quizzes for Numerical Methods.  An example of that is here – right click to “View Page Source”. http://nm.mathforcollege.com/mcquizzes/01aae/quiz_01aae_introduction.html

The above quiz is adequate but looks vintage and I am currently in the process of migrating my whole numerical methods site to WordPress.  As part of this migration, I tried to update the JavaScript code to work on WordPress but that turned out to be above my pay grade.

After much searching, I found the WATU quiz plugin and am using it to redevelop the quizzes from scratch with much of the text being cut and paste from old quizzes.

WATU is quite versatile but I faced issues with rendering of the equations.  For that I use the WP-Katex plugin.  Simply put the equations between the  tagname latex in brackets []  followed by /latex in brackets [], and this shortcode works.  I would show an example to illustrate the use of the shortcode, but it gets rendered.  See usage here.

This use of latex shortcode worked well for the question statements in the quiz but when latex shortcode was put in the distractors, equations would show up with weird spacing.  This was resolved quickly by WATU support where they suggested to edit the WATU style.css file.  See https://wordpress.org/support/topic/latex-not-displaying-properly-in-multiple-choice-answers/ for the solution.  It worked.

Now, another Latex issue cropped up when a user would submit a quiz  and it shows the right answers to the user.  The equations written in Latex would not get rendered and instead it would show the linear form of the equations.   Those were resolved by going to general settings in the WATU quizzes and check marking quizzes to not use Ajax.

WATU is a complete solution for posting online quizzes on the web for student practice.  I am not using WATU to collect data or to assign a grade, but these capabilities do exist in WATU.

See the new version of the quiz I created now on WordPress: https://numericalmethods.autarkaw.com/quiz-chapter-01-01-introduction-to-numerical-methods-2/  Please do not bookmark the quiz as this is a test website and I will be migrating the test website to the original site (http://mathforcollege.com) by the time Fall semester starts.  This will create the least disruption to maintain legacy of open course ware.