Graduate Thesis Or Dissertation
 

A fast algorithm for determining the primitivity of an n x n nonnegative matrix

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/ff365753t

Descriptions

Attribute NameValues
Creator
Abstract
  • Nonnegative matrices have a myriad of applications in the biological, social, and physical genres. Of particular importance are the primitive matrices. A nonnegative matrix, M, is primitive exactly when there is a positive integer, k, such that M[superscript k] has only positive entries; that is, all the entries in M[superscript k] are strictly greater than zero. This method of determining if a matrix is primitive uses matrix multiplication and so would require time Ω(n[superscipt α]) where α>2.3 even if fast matrix multiplication were used. Our goal is to find a much faster algorithm. This can be achieved by viewing a nonnegative matrix, M, as the adjacency matrix for a graph, G(M). The matrix, M, is primitive if and only if G(M) is strongly connected and the greatest common divisor of the cycle lengths in G(M) is 1. We devised an algorithm based in breadth-first search which finds a set of cycle lengths whose gcd is the same as that of G(M). This algorithm has runtime O(e) where e is the number of nonzero entries in M and therefore equivalent to the number of edges in G(M). A proof is given shown the runtime of O(n + e) along with some empirical evidence that supports this finding.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details LeegardAmandaD2003.pdf 2017-08-03 Public Download