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

learn more… | top users | synonyms

3
votes
0answers
18 views

Singularity of a positive linear combination of rank one matrices

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that $$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$ ...
0
votes
0answers
9 views

QR method for Hessenberg matrices

In trying to implement the method, my approach is to use a reduction to Hessenberg form, and then to iterate using a QR method of Givens rotations. However, I am having trouble successfully ...
1
vote
1answer
32 views

Convergence of the LR algorithm for $2\times 2$ SPD matrices

I've been asked to prove that the following iterations converge to the eigenvalues of SPD $A_0 \in \mathbb{R}^{n \times n}$ $A_0 = \begin{bmatrix}a & b\\ b & c \end{bmatrix}$ with $a \geq ...
0
votes
1answer
13 views

efficient computation of Cholesky decomposition during tridiagonal matrix inverse

I have a symmetric, block tridiagonal matrix $A$. I am interested in computing the Cholesky decomposition of $A^{-1}$ (that is, I want to compute $R$, where $A^{-1}=RR^T$). I know how to compute the ...
0
votes
1answer
22 views

Relationship between eigenvectors of two matrices

Suppose I have matrix $A \in R^{2n \text{x} 2n} $ given by $X^{-1} diag(W - iY, W + iY) X$ and matrix $B \in C^{n \text{x} n}$ and $B = W + iY$. Let $v$ be an eigenvector of $A$. How can I relate ...
1
vote
1answer
28 views

Hessenberg reduction

Given $A \in \mathbb{R}^{nxn}$ and $z \in \mathbb{R}^n$, find orthogonal $Q$ such that $Q^TAQ$ is upper Hessenberg and $Q^Tz = \beta e_1$. My attempt so far, Individually I can find the Householder ...
2
votes
1answer
56 views

double root and newton method, a problem on solved exercise? [on hold]

$f(x)$ in $x= \alpha$ has double roots and define in $\alpha$ neighbor. if the sequence $\{x_n\}$ for solving $f(x)=0$ calculated by newton methods the following is correct. ($a$ and $b$ is plasced ...
1
vote
1answer
59 views

questions on polynomial Lagrange Interpolation of order $n$?

I ran in One Ex in my book when I‌ prepare for final exam on numerical method. how can help me how we solve such a problem? if $P(x)$ and $Q(x)$ be two polynomial Lagrange Interpolation of order $n$ ...
1
vote
2answers
29 views

solving given linear equation

So before you guys judge me, I honestly am so clueless with this so please bare with my dumb questions. I have been at this equation that I've been going for an hour now, $\frac{(3x-1)}{2} -2 = ...
-4
votes
0answers
42 views

Positive solutions to $A^T A x \geq 0$ [on hold]

Find a positive solution $x$ to the linear inequality $A^T A x \geq 0$. $A$ is an arbitrary matrix. I was wondering if there is a general solution. EDIT: One special solution is when $A^TA$ is row ...
3
votes
0answers
53 views

How do I apply this PDE as an image filter?

I'm trying to preprocess a height map image with a helmholtz-type equation as described in this paper. The equation is: $$ddx(h') + ddy(h') + y(h'-h) = 0$$ I solved for h and got: ...
0
votes
2answers
41 views

How to minimize $w^{T}Aw$?

$A$ is $n\times n$ matrix. Find a $w$ ( $n$-dimensional unit vector) which minimizes this function. By $w^{T}$, I mean $w$-transpose. I understand there would be non-linear optimization techniques ...
0
votes
2answers
25 views

Decomposition of a diagonal matrix into a product of particular matrices.

Could you tell me please, if it's possible to find a decomposition of a diagonal matrix $ 3 \times 3 $ : $ D ( \lambda_1 , \lambda_2 , \lambda_3 ) = \begin{pmatrix} \lambda_1 & 0 & 0 \\ 0 ...
0
votes
0answers
18 views

Generate duplicate element from a matrix by formula $b(i:j)=A(i:j,:) \times A^{-1} \times b$

I have an interesting question about generate duplicate elements from matrix. I assume that I have a matrix A (such as the bellow example $5 \times 5$) and vector $b$ is $5 \times 1$. My goal is make ...
1
vote
1answer
59 views

Properties shared by similar and unitary similar matrices.

We know that matrices $A$ and $B$ are similar if there exists an invertible matrix $P$ such that $A=PBP^{-1}$ and they are unitarily similar if $P$ is unitary ($PP^*=P^*P=I$). I want to know : What ...
2
votes
1answer
46 views

SVD and transpose of a skinny matrix

Show: If $\mathbf{A}\in\mathbb{R}^{M\times N}$ with $M\geq N$, then there exists a matrix $\mathbf{G}$ with orthonormal rows so that $\mathbf{A}^T=\mathbf{G}\mathbf{A}\mathbf{G}$. I'm pretty lost on ...
0
votes
1answer
31 views

Deducing a formula for multiplying a tri-diagonal symmetrical matrix with vectors

This is more like a math-programming problem, dealing with memory efficiency, but I thought it would be nice to expose it here. Let $A \in \mathbb{R}^{n \times n}$ be a tri-diagonal symmetrical ...
0
votes
1answer
52 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
23 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
38 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
39 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
16 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
32 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
34 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
24 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
33 views

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

For $A \in \mathbb{R}^{m\times n} : m > n, A$ has full rank, I want to show that $k(A^T 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
31 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
32 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
38 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
52 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
40 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
41 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
38 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
62 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
27 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
39 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
50 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
28 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
30 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
44 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
34 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
31 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
41 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
27 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
11 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
96 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
36 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
19 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
18 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
19 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 = ...