BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Mustafa Elsheikh appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Conditions are established under which the $p$-adic valuations of the invariant factors (diagonal entries of the Smith form) of an integer matrix are equal to the $p$-adic valuations of the eigenvalues. It is then shown that this correspondence is the typical case for "most" matrices; precise density bounds are given for when the property holds, as well as easy transformations to this typical case.
For a prime $p$ and a matrix $A \in \mathbb{Z}^{n \times n}$, write $A$ as $A = p (A \,\mathrm{quo}\, p) + (A \,\mathrm{rem}\, p)$ where the remainder and quotient operations are applied element-wise. Write the $p$-adic expansion of $A$ as $A = A^{[0]} + p A^{[1]} + p^2 A^{[2]} + \cdots$ where each $A^{[i]} \in \mathbb{Z}^{n \times n}$ has entries between $[0, p-1]$. Upper bounds are proven for the $\mathbb{Z}$-ranks of $A \,\mathrm{rem}\, p$, and $A \,\mathrm{quo}\, p$. Also, upper bounds are proven for the $\mathbb{Z}/p\mathbb{Z}$-rank of $A^{[i]}$ for all $i \ge 0$ when $p = 2$, and a conjecture is presented for odd primes.
We present algorithms to compute the Smith Normal Form of matrices over two families of local rings. The algorithms use the \emph{black-box} model which is suitable for sparse and structured matrices. The algorithms depend on a number of tools, such as matrix rank computation over finite fields, for which the best-known time- and memory-efficient algorithms are probabilistic. For an $\nxn$ matrix $A$ over the ring $\Fzfe$, where $f^e$ is a power of an irreducible polynomial $f \in \Fz$ of degree $d$, our algorithm requires $\bigO(ηde^2n)$ operations in $\F$, where our black-box is assumed to require $\bigO(η)$ operations in $\F$ to compute a matrix-vector product by a vector over $\Fzfe$ (and $η$ is assumed greater than $\Pden$). The algorithm only requires additional storage for $\bigO(\Pden)$ elements of $\F$. In particular, if $η=\softO(\Pden)$, then our algorithm requires only $\softO(n^2d^2e^3)$ operations in $\F$, which is an improvement on known dense methods for small $d$ and $e$. For the ring $\ZZ/p^e\ZZ$, where $p$ is a prime, we give an algorithm which is time- and memory-efficient when the number of nontrivial invariant factors is small. We describe a method for dimension reduction while preserving the invariant factors. The time complexity is essentially linear in $μn r e \log p,$ where $μ$ is the number of operations in $\ZZ/p\ZZ$ to evaluate the black-box (assumed greater than $n$) and $r$ is the total number of non-zero invariant factors. To avoid the practical cost of conditioning, we give a Monte Carlo certificate, which at low cost, provides either a high probability of success or a proof of failure. The quest for a time- and memory-efficient solution without restrictions on the number of nontrivial invariant factors remains open. We offer a conjecture which may contribute toward that end.