A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive(respectively, negative, zero) entry of B by + (respectively, -, 0). For a sign pattern matrix A, the sign pattern class of A, denoted Q(A), is defined as {B: sgn(B) = A}. An n by n sign pattern matrix A requires all distinct eigenvalues if every real matrix whose sign pattern is represented by A has n distinct eigenvalues. In this thesis, a number of sufficient and/or necessary conditions for a sign pattern to reuiqre all distinct eigenvalues are reviewed. In addition, for n=2 and 3, the n by n sign patterns that require all distinct eigenvalues are surveyed. We determine most of the 4 by 4 irreducible sign patterns that require four distinct eigenvalues.

DSJM is a software toolkit written in portable C++ that enables direct determination of sparse Jacobian matrices whose sparsity pattern is a priori known. Using the seed matrix S 2 Rn×p, the Jacobian A 2 Rm×n can be determined by solving AS = B, where B 2 Rm×p has been obtained via finite difference approximation or forward automatic differentiation. Seed matrix S is defined by the nonzero unknowns in A. DSJM includes well-known as well as new column ordering heuristics. Numerical testing is highly promising both in terms of running time and the number of matrix-vector products needed to determine A. / x, 71 leaves : ill. ; 29 cm

This research introduces a row compression and nested product decomposition of an nxn hierarchical representation of a rank structured matrix A, which extends the compression and nested product decomposition of a quasiseparable matrix. The hierarchical parameter extraction algorithm of a quasiseparable matrix is efficient, requiring only O(nlog(n))operations, and is proven backward stable. The row compression is comprised of a sequence of small Householder transformations that are formed from the low-rank, lower triangular, off-diagonal blocks of the hierarchical representation. The row compression forms a factorization of matrix A, where A = QC, Q is the product of the Householder transformations, and C preserves the low-rank structure in both the lower and upper triangular parts of matrix A. The nested product decomposition is accomplished by applying a sequence of orthogonal transformations to the low-rank, upper triangular, off-diagonal blocks of the compressed matrix C. Both the compression and decomposition algorithms are stable, and require O(nlog(n)) operations. At this point, the matrix-vector product and solver algorithms are the only ones fully proven to be backward stable for quasiseparable matrices. By combining the fast matrix-vector product and system solver, linear systems involving the hierarchical representation to nested product decomposition are directly solved with linear complexity and unconditional stability. Applications in image deblurring and compression, that capitalize on the concepts from the row compression and nested product decomposition algorithms, will be shown.

Este trabalho tem como objetivo central a elaboração, implementação e reflexão sobre uma sequência didática para o estudo de matrizes a partir de tranformações geométricas. A sequência didática pretende propiciar ao aluno um estudo que justifique as definições das operações entre matrizes e suas respectivas propriedades, a partir da observação e análise de algumas transformações geométricas, de modo a se refazer o processo histórico da definição e obtenção desses conceitos. Além disso apresenta algumas atividades de aplicação de matrizes, onde a composição e iteração de transformações geométricas no software Shapari geram algumas figuras fractais. Como metodologia de trabalho adotamos a engenharia didática para a elaboração, implementação e avaliação da didática proposta. O texto também apresenta a análise das referências sobre o ensino de matrizes e tranformações geométricas. Começando pelas orientações dos documentos oficiais e passando pela apresentação de diversos estudos sobre o tema delimitamos e justificamos a nossa proposta de ensino. Além disso, apresentamos um extrato sobre o conhecimento matemático envolvido no tema, de modo que sirva de base para o docente que implementar a seuência didática em sala de aula. / This work has as its main goal the formulation, implementation and contemplation of a didactie sequence to the study of matrices from geometric transformations. The didactic sequence intends to propitiate the student a study which justifies the definitions of operations between matrices and their respective properties, from the observation and analysis of some geometrie transformations, so that they are able to redo the historical process of the definition and the acquisition of these concepts. Besides that, it shows some activities to the application of matrices, in which the composition and interation of geometric transformations in the Shapari software generate some fractals. We have adopted Didactic Engineering as a methodology to the elaboration, implementation and evaluation of the proposed didactic sequence. The text also shows an analysis of the references about the teaching of matrices and the geometric transformations. We delimited and justified our teaching proposal by staring with orientations of official documents and showing a series of studies about the theme. Besides that, we show an excerpt about the mathematical knowledge involved in the theme, so that, it can be used as basis to the teacher who decides to implement the didactic sequence in the classroom.

Este trabalho tem como objetivo central a elaboração, implementação e reflexão sobre uma sequência didática para o estudo de matrizes a partir de tranformações geométricas. A sequência didática pretende propiciar ao aluno um estudo que justifique as definições das operações entre matrizes e suas respectivas propriedades, a partir da observação e análise de algumas transformações geométricas, de modo a se refazer o processo histórico da definição e obtenção desses conceitos. Além disso apresenta algumas atividades de aplicação de matrizes, onde a composição e iteração de transformações geométricas no software Shapari geram algumas figuras fractais. Como metodologia de trabalho adotamos a engenharia didática para a elaboração, implementação e avaliação da didática proposta. O texto também apresenta a análise das referências sobre o ensino de matrizes e tranformações geométricas. Começando pelas orientações dos documentos oficiais e passando pela apresentação de diversos estudos sobre o tema delimitamos e justificamos a nossa proposta de ensino. Além disso, apresentamos um extrato sobre o conhecimento matemático envolvido no tema, de modo que sirva de base para o docente que implementar a seuência didática em sala de aula. / This work has as its main goal the formulation, implementation and contemplation of a didactie sequence to the study of matrices from geometric transformations. The didactic sequence intends to propitiate the student a study which justifies the definitions of operations between matrices and their respective properties, from the observation and analysis of some geometrie transformations, so that they are able to redo the historical process of the definition and the acquisition of these concepts. Besides that, it shows some activities to the application of matrices, in which the composition and interation of geometric transformations in the Shapari software generate some fractals. We have adopted Didactic Engineering as a methodology to the elaboration, implementation and evaluation of the proposed didactic sequence. The text also shows an analysis of the references about the teaching of matrices and the geometric transformations. We delimited and justified our teaching proposal by staring with orientations of official documents and showing a series of studies about the theme. Besides that, we show an excerpt about the mathematical knowledge involved in the theme, so that, it can be used as basis to the teacher who decides to implement the didactic sequence in the classroom.

La Terre est une planète en constante évolution et sa surface ne cesse de se transformer. Ses déformations soulèvent des questionnements. Depuis plusieurs années, le L2G de l’ESGT s’intéresse à l’étude des déformations par inter comparaison de techniques. Il dispose en cela de différents procédés de mesure. Puis au fil du temps, le laboratoire s’interroge sur l’intérêt de réaliser une combinaison entre différentes techniques de mesure afin d’observer des déformations fines et précises (quelques millimètres).L’objectif de cette thèse est de démontrer l’intérêt de combiner des mesures GNSS et des mesures topométriques, celles-ci semblant être les plus utilisées, et de les concrétiser. Les résultats présentés sont basés sur des simulations et sur des campagnes de mesures combinées des techniques de GNSS et de topométrie effectuée sur un réseau test d’une étendue locale. Les calculs évoluent en fonction de la distance de la ligne de base et en modifiant les durées de sessions de mesures. Nous montrons qu’une combinaison par cumul des équations normales améliore la précision du positionnement non seulement par rapport à l’utilisation de chaque technique séparée, mais également par rapport aux méthodes classiques basées sur la combinaison des coordonnées issues des techniques de GNSS et de topométrie. / The Earth is a constantly evolving planet and its surface keeps transforming. Its deformations raise questions. For several years, the L2G at ESGT has been interested in the study of deformations through inter comparison of techniques. For this, it has various measurement processes. Then, with time, the laboratory is now pondering about the interest of combining various techniques of measurement in order to observe fine and precise deformations (a few millimeters).The aim of this PhD thesis is to demonstrate the interest of combining GNSS and topometric measurements, the latter being apparently the most commonly used. The presented results are based on simulations and campaigns of combined measurement through the use of GNSS and topometric techniques made on a model network of a local area. Thecalculations made are dependent both on the distance of the baseline and the alteration of the session length.We show that a combination through the accumulation of the normal equations improves the localisation accuracy regarding not only the use of every separate technique but also the more classic methods based on the coordinates combination provided by GNSS and topometric techniques.

Cette thèse s'inscrit dans le domaine des matrices aléatoires et des techniques de grandes déviations. On s'attachera dans un premier temps à donner des inégalités de déviations pour différentes fonctionnelles du spectre qui reflètent leurs comportement de grandes déviations, pour des matrices de Wigner vérifiant une propriété de concentration indexée par un paramètre alpha ∈ (0,2]. Nous présenterons ensuite le principe de grandes déviations obtenu pour la plus grande valeur propre des matrices de Wigner sans queues Gaussiennes, dans la lignée du travail de Bordenave et Caputo, puis l'étude des grandes déviations des traces de matrices aléatoires que l'on aborde dans trois cas : le cas des beta-ensembles, celui des matrices de Wigner Gaussiennes, et enfin des matrices de Wigner sans queues Gaussiennes. Le cas Gaussien a été l'occasion de revisiter la preuve de Borell et Ledoux des grandes déviations des chaos de Wiener, que l'on prolonge en proposant un énoncé général de grandes déviations qui nous permet donner une autre preuve des principes de grandes déviations des matrices de Wigner sans queues Gaussiennes. Enfin, nous donnons une nouvelle preuve des grandes déviations de la mesure spectrale empirique des beta-ensembles associés à un potentiel quadratique, qui ne repose que sur leur représentation tridiagonale. / This thesis falls within the theory of random matrices and large deviations techniques. We mainly consider large deviations problems which involve a heavy-tail phenomenon. In a first phase, we will focus on finding concentration inequalities for different spectral functionals which reflect their large deviations behavior, for random Hermitian matrices satisfying a concentration property indexed by some alpha ∈ (0,2]. Then we will present the large deviations principle we obtained for the largest eigenvalue of Wigner matrices without Gaussian tails, in line with the work of Bordenave and Caputo. Another example of heavy-tail phenomenon is given by the large deviations of traces of random matrices which we investigate in three cases: the case of beta-ensembles, of Gaussian Wigner matrices, and the case of Wigner matrices without Gaussian tails. The Gaussian case was the opportunity to revisit Borell and Ledoux's proof of the large deviations of Wiener chaoses, which we investigate further by proposing a general large deviations statement, allowing us to give another proof of the large deviations principles known for the Wigner matrices without Gaussian tail. Finally, we give a new proof of the large deviations principles for the beta-ensembles with a quadratic potential, which relies only on the tridiagonal representation of these models. In particular, this result gives a proof of the large deviations of the GUE and GOE which does not rely on the knowledge of the law of the spectrum.

Submitted by ANA KARLA PEREIRA RODRIGUES (anakarla_@hotmail.com) on 2017-08-30T14:02:41Z No. of bitstreams: 1 arquivototal.pdf: 1530287 bytes, checksum: bd20f7e7a563f1aa0ad40d276bc400f9 (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2017-08-30T14:19:18Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 1530287 bytes, checksum: bd20f7e7a563f1aa0ad40d276bc400f9 (MD5) / Made available in DSpace on 2017-08-30T14:19:18Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1530287 bytes, checksum: bd20f7e7a563f1aa0ad40d276bc400f9 (MD5) Previous issue date: 2015-07-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work we discuss the procedures for solving polynomials equations of degree n 4; n 2 N via circulant matrices, highlighting a new perspective to obtain the Cardano- Tartaglia formulae. This brings up a new look on connected subjects, including the elimination of the term of degree (n􀀀1) and the characterization of real polynomials with all real roots. The method is based on searching a circulant matrix whose characteristic polynomial is identical to the one with the same roots we desire to nd. This approach provides us a simple and uni ed method for all equations through degree four. / Neste trabalho abordamos via matrizes circulantes a resolução de equações polinomiais de grau n 4; n 2 N , destacando uma nova perspectiva para obtenção das fórmulas de Cardano-Tartaglia. Além disso, ele oportuniza uma nova maneira de olhar para questões conexas, incluindo a eliminação do termo de grau (n 􀀀 1) e a caracterização de equações reais com todas as raízes reais. O método é baseado na busca de uma matriz circulante cujo polinômio característico seja idêntico ao das raízes que queremos encontrar. Essa metodologia nos fornece um método simples e uni cado para todas equações até quarto grau.

Méthodes numériques pour le calcul des valeurs propres les plus à droite des matrices creuses et non-hermitiennes de très grande taille / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Cette thèse s’intéresse à deux aspects de la cryptologie symétrique liés à l’utilisation de matrices MDS dans les couches de diffusion linéaires de primitives. Une première partie se fonde sur les conceptions de couches de diffusion linéaires de schémas de chiffrement symétrique à partir de matrices MDS. Les associations entre matrices récursives, respectivement circulantes, et polynômes sont calquées pour construire de nouvelles associations entre d’autres structures de matrices et des éléments d’anneaux de polynômes non commutatifs de Ore. À l’instar des matrices récursives et circulantes, ces structures bénéficient d’implémentations matérielles légères. Des codes de Gabidulin dérivent des méthodes de construction directe de telles matrices, optimales en termes de diffusion, proches d’involutions pour l’implémentation. La seconde partie développe une attaque par différenciation de permutations dont l’architecture s’inspire de l’AES. L’utilisation d’une couche de diffusion linéaire locale avec une matrice MDS induit une description macroscopique de la propagation de valeurs de différences à travers les étapes du chiffrement. Des chemins différentiels tronqués apparaissent, qui servent de point de départ à la conception d’attaques rebond. Les travaux présentés généralisent les attaques rebond connues à l’exploitation de chemins différentiels tronqués structurés non issus d’avalanches libres. Cette structure permet de ne pas consommer tous les degrés de libertés au cours d’une seule étape algorithmique mais de les répartir en trois étapes. Une attaque sur 11 tours d’une permutation de Grostl-512 est alors déployée. / This thesis focuses on two aspects of symmetric cryptology related to the use of MDS matrices as building blocks of linear layers for symmetric primitives. A first part handles designs of linear layers for symmetric ciphers based upon MDS matrices. Associations between recursive, respectively circulant, matrices and polynomials are reproduced between other matrix structures and elements in non-commutative polynomial rings of Ore. As for recursive and circulant matrices, those structures come along with lightweight hardware implementations. From Gabidulin codes are derived direct constructions of MDS matrices with properties close to involution from hardware perspectives. The second part is about distinguishing attacks on an exemple of AES-like permutations. The use of some MDS matrix to build the linear layer induces a macroscopic description of differential trails through the different steps of the algorithm computing the permutation. Truncated differential path appears, from which rebound attack are built. Original work here generalizes rebound attack applied on permutations of GROSTL-512 from structured differential path not raised from free propagations of differences. This structure allows not to consume all degrees of freedom in a simple algorithmic step but to divide this comsumption into three algorithmic steps. An attack of a reduced-round version with 11 rounds of one permutation of GROSTL-512 can then be mounted.