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

learn more… | top users | synonyms

0
votes
1answer
21 views

Show if it is lipschitz continuous?

I can't use the mean value theorem to prove this. The problem that I am given is $$ f(x) = (\sqrt{17\pi} )x^2 $$ on the interval $=-10 \le x \le 4$ I know that I have to show that $\lvert f(x_2)-f(...
0
votes
1answer
43 views

System of linear equations: and a small perturbation

If $Ax=b$ and $Ax'=b'$ where $x'$ and $b'$ are $x$ and $b$ with a small perturbation, the following inequality will always hold: $ (\left\lVert x-x' \right\rVert/\left / \lVert x \right\rVert) \le \...
0
votes
1answer
28 views

Find a diagonal matrix D such that the gershgorin disks of the matrix $B=D^{-1}AD$ do not include the origin

I am given that $$ A= \begin{bmatrix} 3 & 4 \\ -5 & 9 \end{bmatrix} $$ Find a diagonal matrix D such that the gerschgorin disks of the matrix $B=D^{-1}AD$ ...
1
vote
1answer
47 views

Factorization algorithm to solve this system?

What is the best factorization algorithm to solve this system? (Best is intended as more stable) $$ AA^Tx = b $$ x, b vectors
0
votes
3answers
74 views

Show that UV is a unitary matrix?

Suppose $U$ and $V$ are unitary matrices of the same size. Show that $UV$ is a unitary matrix. I looked up the definition for unitary matrices in my notes. It says that A matrix is unitary if $UU^*= ...
0
votes
1answer
60 views

Does $A^{-1}$ exist?

Suppose A is similar to the matrix B given below. $$ B= \begin{bmatrix} 7 & 0 & 0 \\ a_{21} & 4 & 0 \\ a_{31} & a_{32} & -0.5 \\ \end{bmatrix} $...
0
votes
4answers
53 views

Show that A is diagonalizable?

Show that A is diagonalizable? That is, show that A is similar to a diagonal matrix, D, by finding a matrix P such that D= $P^{-1}AP$. Show all your work. I already found the eigenvalues and ...
1
vote
1answer
35 views

What is $a_{22}$?

I remember doing this problem in linear algebra where you had to solve for k given the determinant and the rest of the values in the matrix. This problem is a little more complicated. Two of the ...
1
vote
3answers
1k views

What is the minimum and maximum number of eigenvectors?

I am given the eigenvalues of a square, 8x8, matrix. They are all non-zero. I have determined that the matrix is diagonalizable and has an inverse. In one part of the problem, I am asked to find the ...
3
votes
1answer
163 views

Definition of Distinct eigenvalue clarification?

I'm solving a problem where I am given the eigenvalues of a matrix $A$ and need to solve for the determinant of $A$. I know that if my matrix is diagonalizable I can find the determinant of $A$ by ...
0
votes
1answer
92 views

a multiple choice question related to trace of a matrix.

let P and Q are two invertible matrices . and PQ= -QP . then which of the following is true a) trace(P)=trace(Q)=0 c)trace(P) is not equal to trace(Q) c) none of the above. i can show that trace(...
0
votes
2answers
83 views

Simplifying a sum of products related to Vandermonde determinant

How to show this equality? $$ 1=(-1)^n\sum_{k=0}^n\frac{x_k^n}{\prod_{\substack{l=0 \\ l \neq k}}^n(x_l-x_k)} $$ This is part of a proof to show the value of the determinant of the Vandermonde matrix ...
0
votes
1answer
49 views

Any time saving/ short methods to solve this problem?

Three persons A,B,C whose salaries together amount to $144000. Each spend 80,85 & 75 percent of their salaries respectively . If their savings are in the ratio 8:9:20, then C's salary is? ...
1
vote
2answers
54 views

Problem implementing a QR factorization

I'm trying to write a Fortran subroutine to compute a QR factorization using the Householder method. To test my routine, I compute the factorization of the following matrix: $$ A = \begin{pmatrix} ...
2
votes
1answer
37 views

LU factorization accuracy

I'm doing some experiments with LU factorization (without pivoting). Basically I have a 2x2 matrix and a $b$ vector and I try to solve Ax=b. $A$ looks like: \begin{pmatrix}a&1\\1&1\\ \end{...
1
vote
0answers
15 views

Reduction of matrix $A$ to $B$ to find eigenvalues by Power method [duplicate]

How to reduce matrix $A$ to $B$ such that it has all eigenvalues and eigenvectors of $A$ but the dominant eigenvalue (eigenvalue with largest magnitude) is replace by $0$ ? I am using Power method to ...
0
votes
0answers
42 views

Implementing specific SVD algorithms

My goal is to learn to implement the two-sided Jacobi SVD, a method of SVD for bidiagonal matrices, and a method of SVD for tridiagonal matrices. Can anyone recommend a place to learn about these, or ...
-4
votes
1answer
47 views

Linear Algebra - minimal polynomial, polynomial

the minimal polynomial of $A$ is $(x−1)(x+1)$. Let $f(x)=4x^{2008} − 8x^{597} + 10x + 6$ show $f(A) = \alpha I + \beta A$ $\alpha=?\ \beta=?$ So I worked on a bit, and I got this far $A = ...
1
vote
0answers
69 views

SVD of a block partitioned matrix

Given a block partitioned matrix $\boldsymbol{A}$ $$ \boldsymbol{A} = \begin{bmatrix} \boldsymbol{A}_{1,1} & \boldsymbol{A}_{1,2} & \cdots \\ \boldsymbol{A}_{2,1} & \boldsymbol{...
2
votes
2answers
55 views

convergence of iterative methods for linear system

Here is a theorem about convergence of iterative methods for linear system in Burden and Faires' book "Numerical Analysis" For any $x_0 \in \mathbb{R}^n$, the sequence defined by $x^k = Tx_{k-1} + c$ ...
1
vote
3answers
175 views

What is the intuition behind matrix splitting methods (Jacobi, Gauss-Seidel)?

Descent Methods, like Gradient and Conjugate Gradient ones, have a nice geometric interpretation and I really love them. What about Jacobi, Gauss-Seidel or other matrix splitting methods? I can't see ...
0
votes
1answer
39 views

Diagonal of multidimensional DFT

If $X$ is a $n\times n$ square matrix and $F$ its Discrete Fourier Transform, is there a way to compute the diagonal $(F_{1,1},\ldots,F_{n,n})$ without explicitly computing the full DFT? How about ...
2
votes
1answer
33 views

How to prove that the inner product is positive unless $Ax = b$?

Suppose $Ax =b$, then the equation above = $0$ Spp $Ax \neq b$, since $A$ is positive definite, then Am I going to the right direction for this proof? How can I show the rest is positive as well?
0
votes
1answer
49 views

Sum of orthogonal matrices

Consider the subspace $\mathbb{R}^m$ with usual inner product.Let $S_1$ and $S_2$ subspaces of $R^m$, $P_1\in M_m(\mathbb{R})$ the orthogonal projection matrix on $S_1$ and $P_2\in M_m(\mathbb{R})$ ...
4
votes
0answers
158 views

What does affine invariance mean in the context of the Newton's method?

The textbook Numerical Solution of Boundary Value Problems for Ordinary Differential Equations (by Ascher, Mattheij, and Russell) states on page 329: [W]e observe that Newton's method is affine ...
1
vote
1answer
39 views

Show that a positive definite (not necessarily symmetric) matrix induces a hyperellipse

Consider $A\in M_n(\mathbb{R})$ a positive definite matrix and a matrix $B\in M_{n \times p}(\mathbb{R})$, with $n\geq p$ and $rank(B)=p$. i) Show that $C=B^TAB$ is positive definite. ii) Show that ...
1
vote
1answer
41 views

Problem with Broyden update: Divide by a matrix?

I am implementing a maximum likelihood method (the EM algorithm) for which I'm using Broyden's method at each iteration. Here is the formula: $\Delta A = \frac{(\Delta \theta - A \Delta\tilde{g})\...
3
votes
1answer
122 views

Find desired root (based on certain constraints) while using Newton-Raphson method

My function is a vector of dimension 6, and on using Newton Raphson method, the solution usually converges to the nearest root. However, I know that my function has multiple roots (it's an Inverse ...
1
vote
0answers
418 views

Really confused about LU decomposition and Doolittle algorithm

I'm really confused about the Doolittle algorithm, so I need some help. At the end of the description at wikipedia, it says It is clear that in order for this algorithm to work, one needs to ...
1
vote
0answers
79 views

Question on the uniqueness of LU decomposition

Let $A \in \mathbb{K}^{n \times n}$ a matrix, and suppose that we can run the Gaussian elimination on $A$ without row or column interchange, so there exist the $LU$ decomposition of $A$. We define ...
7
votes
1answer
86 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
172 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
44 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
211 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
61 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
77 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 ...
1
vote
1answer
83 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
31 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 = 5-\...
3
votes
0answers
84 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: $$\dfrac{ddx(h')}{...
0
votes
2answers
59 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
37 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 &...
2
votes
1answer
162 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
59 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
216 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
578 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
198 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
65 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
217 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
2answers
45 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
50 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 &...