1,721,145 research outputs found
A note on matrix displacement decomposition
No full textThe theory underlying certain representations of a matrix as sum of products of
matrices in algebras is here revisited with the aim of reducing it at its very heart.
In this way we obtain a simple and general theorem that extends some known
results
Algebras in matrix spaces with displacement structure
No full textWe introduce the problem of the location of the algebras
contained in a matrix space with displacement structure.
We present some partial solutions of the problem that
unify and generalize various results obtained so far for the spaces of Toeplitz, Loewner and Toeplitz plus Hankel matrices
Algebras of higher dimension for displacement decomposition and computation with Toeplitz plus Hankel matrices
No full textUsing the concept of displacement rank, we suggest new formulas for the
representation of a matrix in the form of a sum of products of matrices belonging to
two particular matrix algebras having dimension about 2n and being noncommutative.
So far, only n-dimensional commutative matrix algebras have been used in this kind of
applications. We exploit the higher dimension of these algebras in order to reduce,
with respect to other decompositions, the number of matrix products that have to be
added for representing certain matrices. Interesting results are obtained in particular
for Toeplitz-plus-Hankel-like matrices, a class that includes, for example, the inverses
of Toeplitz plus Hankel matrices. Actually, the new representation allows us to
improve the complexity bounds for the product, with preprocessing, of these matrices
by a vector
The Moore-Penrose inverse of the normalized graph Laplacian
No full textWe prove a formula that relates the Moore-Penrose inverses of two matrices A, B such that A = N^(- 1) B M^(-1) and discuss some applications, in particular to the representation of the Moore-Penrose inverse of the normalized Laplacian of a graph. The Laplacian matrix of an undirected graph is symmetric and is strictly related to its connectivity properties. However, our formula applies to asymmetric matrices, so that we can generalize our results for asymmetric Laplacians, whose importance for the study of directed graphs is increasing
Generalized inverses of band matrices
Full text linkIn 1959 Edgar Asplund presented a geometric lemma that largely anticipated many results on the structure of inverses of band matrices. In this note we discuss an extension of Asplund's lemma that addresses the concept of generalized inverse,in particular the Moore-Penrose inverse
A MULTIPARAMETER MODEL FOR LINK ANALYSIS OF CITATION GRAPHS
No full textWe propose a family of Markov chain-based models for the link analysis of scientic publications. The PageRank-style model and the dummy paper model discussed in [Electron. Trans. Numer. Anal., 33 (2008), pp. 1.16] can be obtained by a particular choice of its parameters. Since scientic publications can be ordered by the date of publication it is natural to assume a triangular structure for the adjacency matrix of the citation graph. This greatly simplies the updating of the ranking vector if new papers are added to the database. In addition by assuming that the citation graph can be modeled as a fixed degree sequence random graph we can obtain an explicit estimation of the behavior of the entries of the ranking vector
Approximations of the generalized inverse of the graph Laplacian matrix
No full textWe devise methods for finding approximations of the generalized inverse of
the graph Laplacian matrix, which arises in many graph-theoretic applications.
Finding this matrix in its entirety involves solving a matrix inversion problem,
which is resource demanding in terms of consumed time and memory and hence
impractical whenever the graph is relatively large. Our approximations use only
few eigenpairs of the Laplacian matrix and are parametric with respect to this
number, so that the user can compromise between effectiveness and efficiency
of the approximated solution. We apply the devised approximations to the the
problem of computing current-flow betweenness centrality on a graph. However,
given the generality of the Laplacian matrix, many other applications can be
sought. We experimentally demonstrate that the approximations are effective
already with a constant number of eigenpairs. These few eigenpairs can be
stored with a linear amount of memory in the number of nodes of the graph
and, in the realistic case of sparse networks, they can be efficiently computed
using one of the many methods for retrieving few eigenpairs of sparse matrices
that abound in the literature
Resistance distance, closeness, and betweenness
No full textIn a seminal paper Stephenson and Zelen (1989) rethought centrality in networks proposing an information-theoretic distance measure among nodes in a network. The suggested information distance diverges from the classical geodesic metric since it is sensible to all paths (not just to the shortest ones) and it diminishes as soon as there are more routes between a pair of nodes. Interestingly, information distance has a clear interpretation in electrical network theory that was missed by the proposing authors. When a fixed resistor is imagined on each edge of the graph, information distance, known as resistance distance in this context, corresponds to the effective resistance between two nodes when a battery is connected across them. Here, we review resistance distance, showing once again, with a simple proof, that it matches information distance. Hence, we interpret both current-flow closeness and current-flow betweenness centrality in terms of resistance distance. We show that this interpretation has semantic, theoretical, and computational benefits
A theory on power in networks
No full textThe eigenvector centrality equation λx = A x is a successful compromise between simplicity and expressivity. It claims
that central actors are those connected with central others. For at least 70 years, this equation has been explored in
disparate contexts, including econometrics, sociometry, bibliometrics, Web information retrieval, and network science.
We propose an equally elegant counterpart: the power equation x = Ax÷, where x÷
is the vector whose entries are the reciprocal of those of x. It asserts that power is in the hands
of those connected with powerless others. It is meaningful, for instance, in bargaining situations, where it is advantageous to be connected to those who have few options. We tell the parallel, mostly unexplored story of this intriguing
equation. In particular, we reveal its intimate relationship with the matrix balancing problem
The componentwise conditioning of the DFT
No full textMixed and componentwise condition numbers are useful in order to understand stability properties of
algorithms for solving structured linear systems. The DFT (discrete Fourier transform) is an
essential building block of these algoritms. We obtain precise estimates of mixed and componentwise
condition numbers of the DFT. To this end we explicitly compute certain unimodular vectors (a
complex vector is said unimodular if the modulus of all its entries is equal to one) whose DFT is
again unimodular
- …
