Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
1answer
196 views

PageRank (power iteration method) convergence rate?

I could not get my head around the idea that the second eigenvalue is the convergence rate. Since the matrix in this application is a Markov matrix (rows/columns sum to one), the largest eigenvalue ...
1
vote
1answer
80 views

How page rank relates to the power iteration method

I do not see how pageRank relates to the power method. Since for the pageRank we are looking for the steady stable state (vector) for a Markov (transition) matrix and the matrix has already an ...
4
votes
1answer
51 views

Laplacian solvers for inversion of large matrices?

I have a large matrix L of size 400,000 $\times $ 400,000 . I'm using this L matrix in the following way. Lin = L$^{-1}$ C = D - B * Lin * B'; B,D are of appropriate sizes. L matrix is ...
0
votes
2answers
75 views

Generalized formula for sum of products.

Q:The sum of all possible products of the first n natural numbers taken two by two is? I did not understand the question as it is.What exactly is being asked?I'd really appreciate an answer ...
0
votes
0answers
19 views

Help Required in eigenvectors for sparse matrix?

I have a large sparse matrix A(~400000,~400000) . If I randomly remove few rows from the matrix will there be considerable change in the eigenvalues and the eigenvector's compared to eigenvector's of ...
0
votes
2answers
37 views

norms of Symmetric Positive Definite Submatrices

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
2
votes
2answers
40 views

Cholesky Factorization with submatrices

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
0
votes
1answer
38 views

Principal Submatrices of a Positive Definite Matrix

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
1
vote
1answer
52 views

showing condition number of a matrix is the square root of $A^\top A$

For $A \in \mathbb{R}^{m\times n} : m > n, A$ has full rank, I want to show that $k(A^\top A) = k(A)^2$, is there a way to do so purely from $k(A)=norm(A) norm(A^\dagger)$? Recall that $A^\dagger ...
1
vote
0answers
53 views

Using Cholesky factorization to solve the system AXA=B

I have been given a problem of solving X, which is an unblurred image, in the system: $$B = A X A \iff X = A^{-1} B A^{-1}$$ Where the matrix A describes the blurring of an image and the matrix B is ...
2
votes
0answers
36 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
0
votes
2answers
72 views

Better Gaussian Elimination for solving $Ax=b$ [closed]

We know that Gaussian Elimination is very popular method to resolve $Ax=b$. Does anyone know better method than Gaussian Elimination in term of time complexity? Second question,if I assume that A is ...
0
votes
1answer
55 views

Is $ \frac{ x^T A A x }{ 1+ x^TAx} $ is upperbounded by the biggest eigenvalue of $A$?

I read somewhere that $$ \frac{ x^T A A x }{ 1+ x^TAx} $$ is bounded by the biggest eigenvalue of $A$, where $x \in \mathbb{R}^d$ and $A \in \mathbb{R}^{d \times d}$ and it is PSD. Anyone see why ...
0
votes
0answers
43 views

Finding a function using first derivative

I have some data about just first derivative of a function. Also, I know a point of this function(e.g. (x1,y1)). How can I obtain the function? All my date are numerical. dev f(x)=[ 580.00 , 479.7308 ...
3
votes
1answer
47 views

What is the upper bound on the error of the solution of a noise perturbed linear system $Mx=b$?

Let $x$ be solution to the following linear system: $$ Mx = b$$ and let $ \tilde{x}$ be the solution to the above linear system with some additive noise: $$ M \tilde{x}= \tilde{b}$$ where ...
0
votes
1answer
45 views

Very High degree Polynomial Roots: How to Cope with Large Values?

I hope I'm not duplicating! I'm wondering how it is possible to find all roots of a polynomial of very high degree (100,1000,1000000, ...) numerically. In all numerical methods, the polynomial is ...
2
votes
0answers
92 views

Express Lagrange polynomial in term of Cauchy matrix

Given 2n distinct real numers $s_1,s_2, \dots, s_n$ and $t_1, t_2, \dots,t_n$ define the $n \times n$ Cauchy matrix $C = C(t,s)$ by $C_{ij} = \frac{1}{t_i - s_j}$. Express the Lagrange interpolation ...
0
votes
0answers
53 views

Normal form calculation

I am working on a problem involves 4 dimensional dynamical system. Is there any ready package (for maple ,matlab...) which calculate the normal form of nonlinear continuous dynamical systems? The ...
2
votes
1answer
44 views

Solving $Ax_2 = \lambda x_1$ and $A^Tx_1 = \lambda x_2$ using SVD

Please using only SVD, I have solved the problem using other methods Solving $Ax_2 = \lambda x_1$ and $A^Tx_1 = \lambda x_2$ using SVD: I am solving this to find $\lambda$ and $x_1,x_2$ To find ...
0
votes
2answers
61 views

Prove that I -xx* is singular if and only x*x = 1

(=>) Suppose I - xx* is singular if and only there is a y such that (I−xx*)y=0, i.e. xx* y=y. Now set λ=x* y. Then y=λx, i.e. xx* λx=λx Thus λx(x* x) = λx => x* x = 1 (<=) Suppose x*x = 1 ...
0
votes
1answer
31 views

Normal Equations error bounds

$A^TAx = A^Tb$ $A^TA\hat{x} = A^Tb + f$ where $\lVert f\rVert \leq cu\lVert A\rVert\lVert b\rVert$ Show that $\frac{\lVert x-\hat{x}\rVert}{\lVert x\rVert} \leq cuK(A)^2\frac{\lVert ...
1
vote
1answer
77 views

Thomas Algorithm for Tridiagonal System

A professor gave us an assignment to solve a Tridiagonal system using Thomas Algorithm. Here is the exercise: I am lost as to what to do with that $(0.2\pi)^2$ and do I just calculate the ...
3
votes
1answer
101 views

Understanding the QR eigenvalue finding algorithm

I'm trying to code up a matrix library (purely as a learning exercise). This question is about the math I'm trying to understand in order to implement it. I just want to make sure I have a firm grasp ...
0
votes
0answers
39 views

Can someone explain how to obtain zeroes for L and U for A=LU factorization?

I understand that,In A=LU, for the L = lower triangular matrix, must have zeroes for all elements above the main diagonal and for U = upper triangular matrix, we need to have all elements as zeroes ...
1
vote
1answer
38 views

Proof of an alternate Matrix Condition Number Representation

I'm currently looking over a section in my textbook on Matrix Condition Numbers and it's given the definition $cond(A) = ||A|| \cdot ||A^{-1}||$ but it's also equated this definition of a condition ...
2
votes
1answer
45 views

Conditioning of Triangular Matrices:

Let $U \in \mathbb{R}^{N\times N}$ be upper triangular. $U$ is well conditioned if the magnitude of the diagonal elements is sufficiently large compared to that of the corresponding off-diagonal ...
0
votes
1answer
45 views

Getting translation and rotation from resultant matrix

I have a matrix which performs a 2D rotation around any given center. Using homogenous coordinates, I have the matrices: $$ T = \begin{pmatrix} 1 & 0 & C_x \\ 0 & 1 & C_y \\ 0 & 0 ...
1
vote
1answer
19 views

Coordinate transformation (or conversion) into yards

Following is a soccer field with its dimensions. There is a similar field, but I am capturing coordinates via mouse-movement. So, what (115,75) shows here, is ...
0
votes
0answers
99 views

QR fatorization for tridiagonal matrices

Let $$A = \left[\begin{array}{rrrr} \delta_1&\gamma_2 & &0 \\ \gamma_2&\delta_2 &\ddots & \\ &\ddots &\ddots &\gamma_n \\ 0 & &\gamma_n ...
3
votes
1answer
43 views

prove that $|\lambda(H) - \lambda(B)| \leq \sqrt{||(C^HC)||_2}$

Let A, B be Hermitian square matrices and $$H = \left[\begin{array}{rr}A & C \\ C^H & B\end{array}\right]$$ Show every eigenvalue $\lambda(B)$ of B, there is an eigenvalue $\lambda(H)$ of H ...
0
votes
1answer
21 views

a matrix inverse problem

Given a matrix $X$, let $D$ be a diagonal matrix whose diagonal elements are row sums of $X$, let $I$ be an identity matrix. Now I have a resultant matrix of $Y=(I-X)^{-1}$, and I would like to ...
1
vote
1answer
22 views

Proof that strictly tri-diagonally dominant matrix has an inverse

We are given the following theorem of which we need only know the result. Theorem Suppose an $n\times n$ matrix $A= (a_{ij})$ is tri-diagonal with $a_{i,i-1}a_{i,i+1} \neq 0$, for each ...
1
vote
1answer
45 views

How does one prove the solution of minimum Euclidean Norm to the least squares problem?

If we have some $m \times n$ matrix $A$ with an $m$-vector $b$, how does one prove that the solution $x$ of the minimum Euclidean norm to the least squares problem $Ax \approx b$ is given by $$ x = ...
1
vote
1answer
52 views

convolution and associativity

Ok Let talk about this,... I am now so confused. 1-$$\mathcal{F}\Big\{c(x-x_0)b(x-x_0)\Big\}=\mathcal{F}\Big\{c(x-x_0)\Big\}\circ\mathcal{F}\Big\{b(x-x_0)\Big\}\\=\Bigg[e^{-2ix_0y}C(y) ...
0
votes
0answers
28 views

the rank of QR decomposition

I saw this in a paper, where one has a QR decomposition $C=QR$ ($C\in R^{m\times r}$, $Q\in R^{m\times r}$ is column orthogonal, $R\in R^{r\times r}$, $m>r$). However, under the condition that the ...
1
vote
1answer
45 views

Relative error of floating point in inner product

Prove that the floating point arithmetic with machine epsilon $\epsilon$ produces an inner product satisfying: $$\text{fl}(x^Ty) = x^T(y+e)$$ where $$|e_i| \leq 2n\epsilon|y_i|$$ as long as $n\epsilon ...
1
vote
1answer
39 views

Question on the spectral radius, regular splitting, and non-singularity/non-negativity

Given $A$ in $R^{nxn}$ and its regular splitting M and N (A = M - N), $M$ is nonsingular and $M^{-1}$ and $N$ are nonnegative. If the spectral radius $p(M^{-1}N)<1$, show $A$ nonsingular and ...
0
votes
3answers
76 views

How does one find the reduced Singular Value Decomposition of a row or column vector? [duplicate]

If we treat a column vector $a$ as an $n \times 1$ matrix, or a row vector $a^T$ as a $1 \times n$ matrix, how would one write out the reduced singular value decomposition of $a$?
0
votes
4answers
58 views

Is it possible to generate $A$ from a linear system of the form $Ax=b$ given $x$ and $b$?

Take a linear system of the form $Ax=b$. Usually, for obvious reasons, we want to find $x$ given $A$ and $b$. As you all know, the solutions may not be unique, or exist, and many algorithms have been ...
0
votes
1answer
95 views

Practical examples/implementation details for Gauss-Seidel method

I'm having a presentation on Gauss-Seidel iterative method, and although it isn't mandatory , I would like to have some practical examples for this method (a system of linear equations with n>=1000, ...
1
vote
1answer
57 views

How to find Housholder reflection

For example, let say I have a matrix$$ \left(\begin{array}{rrr} 3 & 3 & 0 \\ 0 & 0 & 0 \\ 4 & 1 & 3 \end{array}\right) $$ and the Householder has the form $H = I -2uu^T$, and ...
0
votes
0answers
26 views

Iterated Schur complement for block matrices

Suppose you have got a symmetric block matrix $A = \begin{pmatrix} A_{1,1} & \dots & A_{1,n} \\ \vdots & & \vdots \\ A_{n,1} & \dots & A_{n,n} \end{pmatrix}$ Suppose that ...
1
vote
1answer
103 views

Singular Value Decomposition using Jacobi Method

First time user of the site, so I apologize if my question isn't worded properly. I'm trying to implement the SVD of a square matrix using Algorithm 6 found on this website: ...
1
vote
1answer
47 views

$LDL^T$ decompositon of a symmetric matrix and a matrix determinant expression for the lower triangular entries

Let $n$ be a positive integer, and let $M$ be an integral, symmetric, nonsingular matrix. As $M$ is nonsingular, there exists an $LDL^T$ decomposition such that $D = (d_j)$ is diagonal and ...
4
votes
1answer
73 views

Prove $\min_{i}|\lambda_i| \leq |r_{jj}| \leq \max_{i}|\lambda_i|$

Let A be a normal $n \times n$ matrix with the eigenvalues $\lambda_1,...,\lambda_n$ |A| = |QR|, $|Q^HQ| = I$, $|R| = [r_{ik}]$ upper triangular matrix. Prove: $$\min_{i}|\lambda_i| \leq |r_{jj}| \leq ...
0
votes
0answers
47 views

How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...
0
votes
2answers
84 views

Prove that $q_{ki} = \lambda_1[1+ \mathcal{O}((\frac{\lambda_1}{\lambda_2})^k)] \; \text{for all } i \; \text{with} \; (x_1)_i \neq 0$

Let A be a real symmetric $n x n$ matrix having the eigenvalues $\lambda_i$ with $$|\lambda_1|>|\lambda_2| \geq ... \geq |\lambda_n|$$ and the corresponding eigenvectors $x_1...x_n$ with $x_1^Tx_k ...
0
votes
1answer
25 views

Reformulate this system of equations

I have the following systems of equations: $$ A\cdot g = \mathbb 0\\ G\cdot \mathbb 1 = w$$ $A$ is a $J\cdot I \times J\cdot I$ matrix. $g$ is a $J\cdot I \times 1$ column vector $\mathbb 0$ and ...
3
votes
1answer
66 views

Relationship between the solution to $Ax=b$ and $(A+I)x=b$

I have have a symmetric, tridiagonal, Toeplitz matrix $A$, where $A_{11} = -\frac{1}{2}$ and $A_{21} = 1$, and I need to solve the system $$ (A+I)x=b, $$ numerically where $b$ does not necessarily ...
1
vote
1answer
28 views

Trying to show convergence of a Forward Euler method based on step size restriction

I have shown that for the given ODE system, that when we apply the forward Euler method to something like \begin{align} \mathbf{y'} &= A\mathbf{y} \\ \mathbf{y}(t_{0}) &= y_{0} \\ t &\in ...