Apresentamos o valor de Perron combinatório de árvores, definido por Andrade e Dahl [4]. Este novo parâmetro é uma cota inferior para o valor de Perron e pode ser calculado diretamente da árvore, sem a necessidade do cálculo do espectro. Exibimos resultados de Kirkland et al. [15] que mostram como a conectividade algébrica de uma árvore pode ser obtida através do valor de Perron. Mostramos que o valor de Perron combinatório é uma boa aproximação para o valor de Perron da estrela e do caminho, conforme afirmado em [4]. Além disso, apresentamos resultados de experimentos computacionais realizados para investigar a qualidade da aproximação do valor de Perron pelo valor de Perron combinatório para árvores com até 14 vértices. Também investigamos a possibilidade de utilizar o valor de Perron combinatório para o ordenamento de árvores de diâmetro 3. / We present the combinatorial Perron value of trees, defined by Andrade and Dahl [4]. This new parameter is a lower bound to the Perron value and it can be computed directly from tree, without the need of spectrum calculation. We exhibit results from Kirkland et al. [15] that show how the the algebraic connectivity of a tree can be obtained through the Perron value. We prove that the combinatorial Perron value is a good approximation to the Perron value of the star and of the path, according to [4]. Besides we present results from computational experiments executed to investigate the quality of the approximation of the Perron value by the combinatorial Perron value for trees with up to 14 vertices. We also investigate the possibility of using the combinatorial Perron value for ordering trees of diameter 3.

A proposta principal desta. dissertação é provar a existência de medidas invariante absolutamente contínuas para uma clas$e de funções monótonas por partes com um número finito de descontinuidade mas o resultado pode ser estedido para funções monótonas por partes com um número infini to de descontinuidades. O método de prova explora a existência de pontos fixos para o operador de Perron- Frobenius e utiliza o Teorema de Helly e o Teorema Ergódico de Kakutani-Yosida. / The main purpose of this dissertation is to prove the existence of invariant absolutely continuous measures for a class of piecewise monotonic functions with a finite number of descontinuities but it can be extended to piecewise monotonic functions with infinite numbers of descontinuities. The method of the proof explores the existence of fixe·d points to Perron-Frobenius operator and employs the Helly's Theorem and the Kakutani - Yosida ergodic Theorem.

A proposta principal desta. dissertação é provar a existência de medidas invariante absolutamente contínuas para uma clas$e de funções monótonas por partes com um número finito de descontinuidade mas o resultado pode ser estedido para funções monótonas por partes com um número infini to de descontinuidades. O método de prova explora a existência de pontos fixos para o operador de Perron- Frobenius e utiliza o Teorema de Helly e o Teorema Ergódico de Kakutani-Yosida. / The main purpose of this dissertation is to prove the existence of invariant absolutely continuous measures for a class of piecewise monotonic functions with a finite number of descontinuities but it can be extended to piecewise monotonic functions with infinite numbers of descontinuities. The method of the proof explores the existence of fixe·d points to Perron-Frobenius operator and employs the Helly's Theorem and the Kakutani - Yosida ergodic Theorem.

A proposta principal desta. dissertação é provar a existência de medidas invariante absolutamente contínuas para uma clas$e de funções monótonas por partes com um número finito de descontinuidade mas o resultado pode ser estedido para funções monótonas por partes com um número infini to de descontinuidades. O método de prova explora a existência de pontos fixos para o operador de Perron- Frobenius e utiliza o Teorema de Helly e o Teorema Ergódico de Kakutani-Yosida. / The main purpose of this dissertation is to prove the existence of invariant absolutely continuous measures for a class of piecewise monotonic functions with a finite number of descontinuities but it can be extended to piecewise monotonic functions with infinite numbers of descontinuities. The method of the proof explores the existence of fixe·d points to Perron-Frobenius operator and employs the Helly's Theorem and the Kakutani - Yosida ergodic Theorem.

Systems whose time evolutions are entirely deterministic can nevertheless be studied probabilistically, <em>i. e. </em> in terms of the evolution of probability distributions rather than individual trajectories. This approach is central to the dynamics of ensembles (statistical mechanics) and systems with uncertainty in the initial conditions. It is also the basis of ergodic theory--the study of probabilistic invariants of dynamical systems--which provides one framework for understanding chaotic systems whose time evolutions are erratic and for practical purposes unpredictable. Delay differential equations (DDEs) are a particular class of deterministic systems, distinguished by an explicit dependence of the dynamics on past states. DDEs arise in diverse applications including mathematics, biology and economics. A probabilistic approach to DDEs is lacking. The main problems we consider in developing such an approach are (1) to characterize the evolution of probability distributions for DDEs, <em>i. e. </em> develop an analog of the Perron-Frobenius operator; (2) to characterize invariant probability distributions for DDEs; and (3) to develop a framework for the application of ergodic theory to delay equations, with a view to a probabilistic understanding of DDEs whose time evolutions are chaotic. We develop a variety of approaches to each of these problems, employing both analytical and numerical methods. In transient chaos, a system evolves erratically during a transient period that is followed by asymptotically regular behavior. Transient chaos in delay equations has not been reported or investigated before. We find numerical evidence of transient chaos (fractal basins of attraction and long chaotic transients) in some DDEs, including the Mackey-Glass equation. Transient chaos in DDEs can be analyzed numerically using a modification of the "stagger-and-step" algorithm applied to a discretized version of the DDE.

Objects such as documents, people, words or utilities, that are related in some way, for instance by citations, friendship, appearance in definitions or physical connections, may be conveniently represented using graphs or networks. An increasing number of such relational databases, as for instance the World Wide Web, digital libraries, social networking web sites or phone calls logs, are available. Relevant information may be hidden in these networks. A user may for instance need to get authority web pages on a particular topic or a list of similar documents from a digital library, or to determine communities of friends from a social networking site or a phone calls log. Unfortunately, extracting this information may not be easy. This thesis is devoted to the study of problems related to information extraction in large graphs with the help of dominant vectors of nonnegative matrices. The graph structure is indeed very useful to retrieve information from a relational database. The correspondence between nonnegative matrices and graphs makes Perron--Frobenius methods a powerful tool for the analysis of networks. In a first part, we analyze the fixed points of a normalized affine iteration used by a database matching algorithm. Then, we consider questions related to PageRank, a ranking method of the web pages based on a random surfer model and used by the well known web search engine Google. In a second part, we study optimal linkage strategies for a web master who wants to maximize the average PageRank score of a web site. Finally, the third part is devoted to the study of a nonlinear variant of PageRank. The simple model that we propose takes into account the mutual influence between web ranking and web surfing.

Systems whose time evolutions are entirely deterministic can nevertheless be studied probabilistically, <em>i. e. </em> in terms of the evolution of probability distributions rather than individual trajectories. This approach is central to the dynamics of ensembles (statistical mechanics) and systems with uncertainty in the initial conditions. It is also the basis of ergodic theory--the study of probabilistic invariants of dynamical systems--which provides one framework for understanding chaotic systems whose time evolutions are erratic and for practical purposes unpredictable. Delay differential equations (DDEs) are a particular class of deterministic systems, distinguished by an explicit dependence of the dynamics on past states. DDEs arise in diverse applications including mathematics, biology and economics. A probabilistic approach to DDEs is lacking. The main problems we consider in developing such an approach are (1) to characterize the evolution of probability distributions for DDEs, <em>i. e. </em> develop an analog of the Perron-Frobenius operator; (2) to characterize invariant probability distributions for DDEs; and (3) to develop a framework for the application of ergodic theory to delay equations, with a view to a probabilistic understanding of DDEs whose time evolutions are chaotic. We develop a variety of approaches to each of these problems, employing both analytical and numerical methods. In transient chaos, a system evolves erratically during a transient period that is followed by asymptotically regular behavior. Transient chaos in delay equations has not been reported or investigated before. We find numerical evidence of transient chaos (fractal basins of attraction and long chaotic transients) in some DDEs, including the Mackey-Glass equation. Transient chaos in DDEs can be analyzed numerically using a modification of the "stagger-and-step" algorithm applied to a discretized version of the DDE.

This is a literature study, in linear algebra, about positive and nonnegative matrices and their special properties. We say that a matrix or a vector is positive/nonnegative if all of its entries are positive/nonnegative. First, we study some generalities and become acquainted with two types of nonnegative matrices; irreducible and reducible. After exploring their characteristics we investigate and prove the two main theorems of this subject, namely Perron's and Perron-Frobenius' theorem. In short Perron's theorem from 1907 tells us that the spectral radius of a positive matrix is a simple eigenvalue of the matrix and that its eigenvector can be taken to be positive. In 1912, Georg Frobenius generalized Perron's results also to irreducible nonnegative matrices. The two theorems have a wide range of applications in both pure mathematics and practical matters. In real world scenarios, many measurements are nonnegative (length, time, amount, etc.) and so their mathematical formulations often relate to Perron-Frobenius theory. The theory's importance to linear dynamical systems, such as Markov chains, cannot be overstated; it determines when, and to what, an iterative process will converge. This result is in turn the underlying theory for the page-ranking algorithm developed by Google in 1998. We will see examples of all these applications in chapters four and five where we will be particularly interested in different types of Markov chains.  The theory in this thesis can be found in many books. Here, most of the material is gathered from Horn-Johnson [5], Meyer [9] and Shapiro [10]. However, all of the theorems and proofs are formulated in my own way and the examples and illustrations are concocted by myself, unless otherwise noted. / Det här är en litteraturstudie, inom linjär algebra, om positiva och icke-negativa matriser och deras speciella egenskaper. Vi säger att en matris eller en vektor är positiv/icke-negativ om alla dess element är positiva/icke-negativa. Inledningsvis går vi igenom några grundläggande begrepp och bekanta oss med två typer av icke-negativa matriser; irreducibla och reducibla. Efter att vi utforskat deras egenskaper så studerar vi och bevisar ämnets två huvudsatser; Perrons och Perron-Frobenius sats. Kortfattat så säger Perrons sats, från 1907, att spektralradien för en positiv matris är ett simpelt egenvärde till matrisen och att dess egenvektor kan tas positiv. År 1912 så generaliserade Georg Frobenius Perrons resultat till att gälla också för irreducibla icke-negativa matriser.  De två satserna har både många teoretiska och praktiska tillämpningar. Många verkliga scenarios har icke-negativa mått (längd, tid, mängd o.s.v) och därför relaterar dess matematiska formulering till Perron-Frobenius teori. Teorin är betydande även för linjära dynamiska system, såsom Markov-kedjor, eftersom den avgör när, och till vad, en iterativ process konvergerar. Det resultatet är i sin tur den underliggande teorin bakom algoritmen PageRank som utvecklades av Google år 1998. Vi kommer se exempel på alla dessa tillämpningar i kapitel fyra och fem, där vi speciellt intresserar oss för olika typer av Markov-kedjor. Teorin i den här artikeln kan hittas i många böcker. Det mesta av materialet som presenteras här har hämtats från Horn-Johnson [5], Meyer [9] och Shapiro [10]. Däremot är alla satser och bevis formulerade på mitt eget sätt och alla exempel, samt illustrationer, har jag skapat själv, om inget annat sägs.

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.

Given a random dynamical system T constructed from Jablonski transformations, consider its Perron-Frobenius operator P_T. We prove a weak form of the Lasota-Yorke inequality for P_T and thereby prove the existence of BV- invariant densities for T. Using the Spectral Decomposition Theorem we prove that the support of an invariant density is open a.e. and give conditions such that the invariant density for T is unique. We study the asymptotic behavior of the Markov operator P_T, especially when T has a unique absolutely continuous invariant measure (ACIM). Under the assumption of uniqueness, we obtain spectral stability in the sense of Keller. As an application, we can use Ulam's method to approximate the invariant density of P_T.