The Non-Negative –Matrix Completion Problem for 5×5 Matrices Specifying Cyclic Diagraphs with 5 Vertices and 4 Arcs

  • Paul M Mwangi P.O Box 60408 , Nairobi, 00200, Kenya
  • Waweru Kamaku P.O Box 60408 , Nairobi, 00200, Kenya
  • Lewis Nyaga P.O Box 60408 , Nairobi, 00200, Kenya
Keywords: graph, subgraph, directed graph, cyclic digraph, acyclic digraph, complete digraph, path, cycle, zero completion, isomorphic, partial matrix, sub-matrix, principal minor, -matrix, non-negative -matrix.


The non-negative P0-matrix completion is considered for 5×5 matrices specifying digraphs with p=5 and q=4.The research determines which of the digraphs with p=5 and q=4 and specifying 5×5 partial matrices have non-negative P0-completion. Considering the 5×5 matrices with q=4, all the sixty one (61) non-isomorphic digraphs shall be constructed. All the partial non-negative P0-matrices will be extracted from each digraph. To establish if the pattern has non-negative P0-completion or not, zero completion will be performed on each of the partial matrix extracted. The study establishes that all acyclic digraphs of an 5×5 matrix with q=4 have non-negative P0-completion. The matrix completion problem is to find the values of an n x m matrix M, given a sparse and incomplete set of observations. Possible areas of applications include Seismic data reconstruction to recover missing traces when data is sparse and incomplete ,say due to malfunctioned measuring instruments, biased or corrupted traces, ground barriers, or due to financial limitation to access complete data. Others include incomplete market surveys (eg movie ratings to complete missing data so as to recommend appropriately to viewers), weather forecasting from historical data recordings as well as future predictions from computer simulations, reconstruction of images in computer; and finding the positions of sensors in Global Positioning from distances available in a local network.


Hogben, L. (2001). "Graph Theoretic Methods for Matrix Completion Problems."Linear Algebra and its Applications. Vol.328, pp 161–202.

Choi, J. Y.; Dealba, L.M. ;Hogben, L.; Kivunge, B. M.; Nordstrom, S. K.;& M.Schedenhelm. (2003). "The non-negative Po-matrix completion problem." Electronic Journal of Linear Algebra.Vol.10, pp 46–59.

Munyiri, J.; Kamaku, W.;& Nyaga, L. (2014). "The Non-Negative Po-matrix Completion Problem for 5×5 Matrices Specifying Digraphs with 5 Vertices and 3 Arcs."

Harary, F. & Palmer, E.M. (1973).Graph Enumeration. Michigan State University East Lansing.