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

learn more… | top users | synonyms

0
votes
0answers
98 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 ...
0
votes
0answers
45 views

Implicit Solution of Linear Algebraic Equations with Discontinuities

I am trying to get a reliable algorithm for solving a set of linear algebraic equations involving implicit singularities/discontinuous function. The model equation is: $$ {\bf s}_{n+1} = {\bf s}_n ...
1
vote
1answer
50 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
27 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 ...
3
votes
0answers
62 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 ...
0
votes
1answer
42 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
26 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
46 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
73 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
0answers
29 views

Smallest square problem, $A^*A$ singular?

In our numerics class, we have to solve the smallest square problem $Ax = b$ with $$A = \left( \begin{matrix} 1 & 3 &-4\\ 3 & 9 & -2\\ 4 & 12 & -6\\ 2 & 6 & 2 ...
0
votes
0answers
17 views

Linear Inverse Problem with symmetry constraint

I'm not entirely sure if this is even a solvable problem: $\mathbf{A} = \mathbf{B} \mathbf{C}$ Knowns: $\mathbf{A} \in \Bbb{R}_{n\times m}^{+}$, $\mathbf{B} \in \Bbb{R}_{n\times m}^{+}$ An ...
0
votes
1answer
59 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 ...
0
votes
0answers
75 views

Determining Nullspace Basis so that only one column is deleted or added as a row is added or deleted, with remaining columns of basis staying the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, ...
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
748 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 ...
0
votes
0answers
126 views

the SVD (singular value decomposition) of an augmented matrix

Suppose we have a $4\times 3$ dimensional matrix $A$. Denote the SVD of $A$ by $USV^T$, where $U\in R^{4\times 3}, S\in R^{3\times 3}, V\in R^{3\times 3}$. Then, we construct a new matrix $B=[A;0]\in ...
3
votes
1answer
115 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
0answers
25 views

Upperbound for a linear algebraic ratio?

Consider ($n\times 1$)-column vector $\mathbf{p} = (p_i)_{i=1}^n$ with $p_i > 0$ and a symmetric ($n\times n$)-matrix $\mathbf{A} = [a_{ij}]$ with $a_{ii} = 0$ and $a_{ij} \in [0,1]$ for $i \neq ...
0
votes
0answers
19 views

Backwards Stability of systems

Let $A$ be a nonsingular matrix, let $x_{k+1}$ be an approximation to the solution of $Ax=b$, and let $r^{k+1}=b-Ax^{k+1}$. Show that $x^{k+1}$ is $\epsilon$-backward stable approximate of ...
0
votes
0answers
60 views

Linearize discretized nonlinear system model

For the following nonlinear system I want to find the linearization after a discretization: $$ \begin{pmatrix} \dot{x_{1}} \\ \dot{x_{1}} \\ \dot{x_{1}} \end{pmatrix} = 1/A \begin{pmatrix} ...
0
votes
1answer
88 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 ...
0
votes
2answers
82 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? ...
0
votes
0answers
18 views

sparse, complex, unymetric test-matrix

Can anybody recommend me a sparse, complex, unsymmetric test-matrix (maybe from MartixMarket) which is solvable with a transpose-free QMR without preconditioning in under 1000 iterations?
0
votes
0answers
30 views

How many kind of basis function to approximate an arbitrary function

I am finding a list algorithm to approximate an arbitrary function. Such as Bernstein, he said that a linear combination of Bernstein basis polynomials $$B_n(x) = \sum_{\nu=0}^{n} \beta_{\nu} ...
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
36 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\\ ...
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
41 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
46 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
64 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} & ...
2
votes
2answers
46 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
150 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
38 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
29 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 ...
0
votes
1answer
47 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
115 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
38 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
40 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 ...
3
votes
1answer
118 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
386 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
75 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
145 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
42 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
187 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
54 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 ...