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

learn more… | top users | synonyms

5
votes
1answer
30 views

Proving a property about Gauss-Seidel

This is a homework problem, so please give hints or tips instead of full answers. The problem is as follows: Let $G$ be the iteration matrix of the Gauss-Seidel method; i.e. $$G=I-(D-L)^{-1} A$$...
1
vote
0answers
24 views

Overdetermined system with discrete data.

The setup I have a set of experimental data (subscript 1) which calculates two variables $u_1(x,y,z)$ $v_1(x,y,z)$ I can calculate the three spatial gradients for my two variables ($u_1$ and $v_1$...
1
vote
0answers
54 views

QR Algorithm fails under certain conditions

First of all, i have to admit that i am really knew to this numeric stuff. I have to detect two complex Eigenvalues of a Matrix and therefor i implemented some easy QR-Algorithm with MatLab. I am ...
2
votes
2answers
46 views

Special properties in the direct solving of sparse symmetric linear systems

In the area of computational solving of large sparse linear systems, some solvers specialize only on symmetric sparse matrices, be it positive definite or indefinite as compared to general (non-...
1
vote
0answers
42 views

$Az + B\overline{z}$ as a linear operator

Given two matrices $A,B \in \mathbb{C}^{n\times n}$ with fixed $n\in\mathbb{N}^+$, let us consider the operator $$ L:\mathbb{C}^n \to \mathbb{C}^n,\\ L(z) = Az + B\overline{z}. $$ This operator is not ...
1
vote
0answers
149 views

Row degeneracy in systems of linear equations

I am trying to understand the concept of row degeneracy in a system of linear equations, but having trouble understanding this problem. \begin{align} x+2y+z &= 2 \tag{1} \\ 2x+y+3z &=5 \...
2
votes
1answer
58 views

Solving the linear system $XL + L^TX = M$ efficiently

I'm wondering of an efficient way to solve the following system for the symmetric matrix $X$, given a positive semi-definite matrix $S$ and any matrix $M$: $$ LL^T = S $$ $$ XL + L^TX = M $$ $$ (XL) + ...
1
vote
1answer
484 views

Using linear algebra (e.g. matrix) methods to solve a system of linear inequalities

Say we have the equation $Ax>b$, where $A$ is an M-by-N matrix, $b$ is a known vector of length N, x is an unknown vector of length N, and the inequality sign means that each element of $Ax$ is ...
1
vote
1answer
71 views

Positive linear combinations of intervals

Given two intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1=1-a_0<1$ and a third interval $I=[-a,a]$ where $0<a<\frac{1}2$, when is there an $\alpha,\beta\in\Bbb R$ such that ...
1
vote
0answers
17 views

Enforcing additional constraints in linear equation

In a finite element context, I come up with a sparse "stiffness matrix" $A$ and a corresponding RHS $b$. The goal is now to solve $$Au = b$$ Where $u$ is a coefficient vector of the solution. Now I ...
1
vote
0answers
36 views

Solving System of Linear Equations

These are the two known equations: $$\frac{(I_2+I_3)-(I_1+I_4)}{I_1+I_2+I_3+I_4} = \frac{2x}{L}$$ $$\frac{(I_2+I_4)-(I_1+I_3)}{I_1+I_2+I_3+I_4} = \frac{2y}{L}$$ where I know the values of $(x,y,L)$. ...
0
votes
1answer
28 views

Let $f:[-1,1]\to \mathbb{R}$ by $f(x)=x^4$. Determine the polynomial $p_2$ of degree less than or equal to 2 such that $||f-p_2||_2$ is minimal

also compute $||f-p_2||_2$. Write $p_2$ with respect to $\{P_0,P_1,P_2\}$ and $\{1,x,x^2\}$ I know its helpful to show what I have so far but I really don't know where to start. I'm looking at ...
3
votes
1answer
190 views

An Extension to the Generalized Eigenvalue Problem

Given two square matrices $A,B \in \mathbb{R}^{n\times n}$, the generalized eigenvalue problem is finding the scalar $\lambda \in \mathbb{C}$ and vector $x \in \mathbb{C}^{n}$ such that $$ A x=\...
0
votes
1answer
135 views

Complexity of Newton iteration problem for a d-dimensional problem

If we assume that we have $f:\mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ and we want to use the Newton iteration method to solve $f(x)=0_{\mathbb{R}^{d} }$. Is there any theorem regarding the ...
1
vote
1answer
26 views

Polar decomposition varient

I have a factorisation to do, and I think that a varient of Polar decomposition will give me what I need, although I'm not sure of the exact form. I have \begin{equation*} \mathbf{y} = \mathbf{UDU}^*...
0
votes
0answers
116 views

When to use iterative methods for solving systems of linear equation

Iterative methods such as Jacobi, Gauss-Seidel method and successive over relaxation have a very limited field of use - for diagonally dominant matrices. So how they could be used on practice? What is ...
1
vote
1answer
55 views

Generate a random neutrally stable matrix

I need to generate random real matrices such that all eigenvalues have real part equal to 0 -- i.e. random neutrally stable matrices. What's the simplest way to do this? Note that I don't care about ...
0
votes
1answer
30 views

Linear functional and Hessian

Consider the vector space $\mathbb{R}^n$ provided with the usual inner product $<.,.>$. Let $A\in \mathbb{M}_n(\mathbb{R})$ a invertible matrix, $b\in\mathbb{R}^n$ and $J:\mathbb{R}^n\rightarrow ...
0
votes
1answer
36 views

Relationship between centralization and floating-point arithmetic

Suppose I have a problem of least squares where I have $n$ independents regressor variables $x_i$, and suppose I applied the process of centralization and scaling to this variable through $$z_i=\frac{...
3
votes
0answers
63 views

Invertibility of infinite order matrix

how the matrix $[e^{-(x_j-x_k)^2}]$ is invertible where $\{x_j\}$ be any real sequence such that $(x_{j+1}-x_j) >0$ for all $j \in Z$ where $Z$ denotes the set of integers.
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
48 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
75 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
61 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
180 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
98 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
84 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
38 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
16 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
44 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
70 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
58 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
182 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
40 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
50 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
181 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
124 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
428 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
82 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 ...