Some of the theory of nonnegative matrices is first presented. The Perron-Frobenius theorem is highlighted. Some of the important linear algebraic methods of information retrieval are surveyed. Latent Semantic Indexing (LSI), which uses the singular value de-composition is discussed. The Hyper-Text Induced Topic Search (HITS) algorithm is next considered; here the power method for finding dominant eigenvectors is employed. Through the use of a theorem by Sinkohrn and Knopp, a modified HITS method is developed. Lastly, the PageRank algorithm is discussed. Numerical examples and MATLAB programs are also provided.

[pt] Estudaremos dinâmicas simbólicas associadas a alfabetos finitos. Consideraremos seqüências bi-infinitas e espaços com memória finita. Estudaremos propriedades invariantes por conjugação. Analisaremos a relação entre os espaços de seqüências e propriedades de matrizes não negativas. O principal exemplo desta correlação é o Teorema de Perron- Frobenius que relaciona a entropia de um espaço de seqüências e os autovalores de uma matriz não negativa associada ao espaço. Neste contexto, certos grafos e suas propriedades aparecem de forma natural. / [en] We study symbolic dynamics associated to finite alphabets. We consider bi-infinite sequences and spaces with finite memory. We pay attention to properties which are invariant by conjugations. We analyze the relation between spaces of sequences and properties of non-negative matrices. The main example is given by the Perron-Frobenius theorem relating the entropy of a space of sequences and the eigerrvalues of a non-negative matrix associated to the space. In this setting, certain graphs and their properties appear in a natural way.

When a nanostructure is coupled between two leads, the electron transmission probability as a function of energy, E, is used in the Landauer formula to obtain the electrical conductance of the nanodevice. The electron transmission probability as a function of energy, T (E), is calculated from the appropriate solution of the time independent Schrödinger equation. Recently, a large class of nanostructures called quantum dragons has been discovered. Quantum dragons are nanodevices with correlated disorder but still can have electron transmission probability unity for all energies when connected to appropriate (idealized) leads. Hence for a single channel setup, the electrical conductivity is quantized. Thus quantum dragons have the minimum electrical conductance allowed by quantum mechanics. These quantum dragons have potential applications in nanoelectronics. It is shown that for dimerized leads coupled to a simple two-slice (l = 2, m = 1) device, the matrix method gives the same expression for the electron transmission probability as renormalization group methods and as the well known Green's function method. If a nanodevice has m atoms per slice, with l slices to calculate the electron transmission probability as a function of energy via the matrix method requires the solution of the inverse of a (2 + ml) (2 + ml) matrix. This matrix to invert is of large dimensions for large m and l. Taking the inverse of such a matrix could be done numerically, but getting an exact solution may not be possible. By using the mapping technique, this reduces this large matrix to invert into a simple (l + 2) (l + 2) matrix to invert, which is easier to handle but has the same solution. By using the map-and-tune approach, quantum dragon solutions are shown to exist for single-layer planar rectangular crystals with different boundary conditions. Each chapter provides two different ways on how to find quantum dragons. This work has experimental relevance, since this could pave the way for planar rectangular nanodevices with zero electrical resistance to be found. In the presence of randomness of the single-band tight-binding parameters in the nanodevice, an interesting quantum mechanical phenomenon called Fano resonance of the electron transmission probability is shown to be observed.

In Markov chain models in finance and healthcare a transition matrix over a certain time interval is needed but only a transition matrix over a longer time interval may be available. The problem arises of determining a stochastic $p$th root of astochastic matrix (the given transition matrix). By exploiting the theory of functions of matrices, we develop results on the existence and characterization of stochastic $p$th roots. Our contributions include characterization of when a real matrix hasa real $p$th root, a classification of $p$th roots of a possibly singular matrix,a sufficient condition for a $p$th root of a stochastic matrix to have unit row sums,and the identification of two classes of stochastic matrices that have stochastic $p$th roots for all $p$. We also delineate a wide variety of possible configurationsas regards existence, nature (primary or nonprimary), and number of stochastic roots,and develop a necessary condition for existence of a stochastic root in terms of the spectrum of the given matrix. On the computational side, we emphasize finding an approximate stochastic root: perturb the principal root $A^{1/p}$ or the principal logarithm $\log(A)$ to the nearest stochastic matrix or the nearest intensity matrix, respectively, if they are not valid ones;minimize the residual $\normF{X^p-A}$ over all stochastic matrices $X$ and also over stochastic matrices that are primary functions of $A$. For the first two nearness problems, the global minimizers are found in the Frobenius norm. For the last two nonlinear programming problems, we derive explicit formulae for the gradient and Hessian of the objective function $\normF{X^p-A}^2$ and investigate Newton's method, a spectral projected gradient method (SPGM) and the sequential quadratic programming method to solve the problem as well as various matrices to start the iteration. Numerical experiments show that SPGM starting with the perturbed $A^{1/p}$to minimize $\normF{X^p-A}$ over all stochastic matrices is method of choice.Finally, a new algorithm is developed for computing arbitrary real powers $A^\a$ of a matrix $A\in\mathbb{C}^{n\times n}$. The algorithm starts with a Schur decomposition,takes $k$ square roots of the triangular factor $T$, evaluates an $[m/m]$ Pad\'e approximant of $(1-x)^\a$ at $I - T^$, and squares the result $k$ times. The parameters $k$ and $m$ are chosen to minimize the cost subject to achieving double precision accuracy in the evaluation of the Pad\'e approximant, making use of a result that bounds the error in the matrix Pad\'e approximant by the error in the scalar Pad\'e approximant with argument the norm of the matrix. The Pad\'e approximant is evaluated from the continued fraction representation in bottom-up fashion, which is shown to be numerically stable. In the squaring phase the diagonal and first superdiagonal are computed from explicit formulae for $T^$, yielding increased accuracy. Since the basic algorithm is designed for $\a\in(-1,1)$, a criterion for reducing an arbitrary real $\a$ to this range is developed, making use of bounds for the condition number of the $A^\a$ problem. How best to compute $A^k$ for a negative integer $k$ is also investigated. In numerical experiments the new algorithm is found to be superior in accuracy and stability to several alternatives,including the use of an eigendecomposition, a method based on the Schur--Parlett\alg\ with our new algorithm applied to the diagonal blocks and approaches based on the formula $A^\a = \exp(\a\log(A))$.