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

learn more… | top users | synonyms

0
votes
0answers
16 views

Is any method which allows segmentation of long diagonalizing procedures?

This is a question for a smarter way of numerical computation. When I diagonalize a certain type of Vandermonde-matrices in Pari/GP ("mateigen(M)"), for instance of size 16x16 then this can be ...
0
votes
1answer
31 views

For which $a \in \mathbb{R}$ Jacobi converge?

I tried to solve the following problem and I don't know if it's correct and I have a few questions: Let \begin{align} A = \left[ {\begin{array}{cc} a & 1 & 0 \\ 1 & a & 1 \\ 0 & ...
0
votes
1answer
59 views

Can a 6-arm star be convex

Please help me with the following question. Suppose that the constant level contours of some function $V:\mathbb{R}^{2} \rightarrow \mathbb{R}$ have the shape of a symmetric 6-arm star. Can such a ...
0
votes
1answer
51 views

Stability analysis of Numerical Method

For a system of ODEs, I'm looking at the case where $$u'=Au$$ where $A$ is diagonalisable so $$u'=R\Lambda R^{-1}u.$$ In the notes I am looking at it goes on to say we can premultiply by $R^{-1}$ so ...
0
votes
0answers
43 views

(Numerical) Cholesky Decomposition of a Product of Matrices

Let $E$ be a symmetric positive definite matrix and let $O$ be an orthonormal matrix i.e. $O^{T}O=I$. Let $chol(A)=L$ such that $A=LL^{T}$ i.e. $chol(.)$ is the operation that returns the lower ...
1
vote
1answer
89 views

Does a Convex Function need to be Continuous

I have been trying the following problem and I am very confused. If possible the problem should be solved with derivatives. If the derivative exists for all the points on the graph then it is ...
0
votes
2answers
140 views

Quadratic Function must be positive definite to have a unique minimum

I have attempted the following question multiple times and I am very confused about the proof please help me solve it. Let $V(x)=a+b^{T}x+\frac{1}{2}x^{T}Cx$ for some $a \in \mathbb{R}, b \in ...
2
votes
2answers
155 views

Power iteration sign of eigenvalue?

I need to write a program which computes all eigenvalues and corresponding eigenvectors. I'd like to use power iterations method (I know that it's not good but it's really necessary). my algorithm ...
0
votes
1answer
41 views

spectral radius of matrix with elements less than one

Assume we have a square matrix A whose elemnts are less than 1, Can we say that its spectral radius is also less than 1. Can we say that the absolute value of its eigenvalues are also less than 1?
3
votes
2answers
70 views

Demonstrate that a matrix has no LU factorization

Have to show that $$\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}$$ has no LU factorization. It seems trivial just to say that this cannot have an LU decomposition because it is a lower ...
0
votes
0answers
47 views

what is the meaning/characteristics of the component-wise product of right and left eigenvectors.

I have a generic, but seemingly simple question : what is the meaning/characteristics of the component-wise product of right and left eigenvectors (for the same eigenvalue of course) ? let's call ...
1
vote
2answers
59 views

eigenvalues for symmetric and non-symmetric matrices

I know the Power methods and Jacobi methods are suitable to finding eigenvalues for symmetric matrices, please tell me other methods for this matrices. And what are the methods for the Non-symmetric ...
0
votes
1answer
64 views

Impossible Schur Factorizations

I am having trouble finding the schur factorization of the following matrix: $A=\begin{pmatrix}3&8 \\ -2&3 \end{pmatrix}$ I followed an algorithm in the book, as well as computing an answer ...
0
votes
0answers
33 views

Tridiagonal Gaussian Elimination: Band Storage

I was given this algorithm for Tridiagonal Gaussian Elimination: Band Storage for i = 2:N if W(3,i-1) is zero error('the matrix is singular or pivoting is required') end m = W(4,i)/W(3,i-1) ...
1
vote
1answer
101 views

Minimizing the Determinant

I would like to minimize the determinant of the following matrix, det(A) $A = (VV^T+\lambda I)^{-1}$ and $\lambda$ is set to be very small.
0
votes
1answer
54 views

Fast Gauss-Seidel convergence on low rank matrices

I stumbled upon the following remarkable fact when experimenting with the Gauss-Seidel iterative solver: First I construct a low-rank symmetric positive semi-definite matrix $A = M^TM$ with M a ...
3
votes
1answer
72 views

Prove this matrix is invertible for $n < m-1$

Prove this $(n+1)\times (n+1)$ matrix $\bf{A}$ is invertible for $n < m-1$ and the $x_k$ distinct, \begin{bmatrix} m &\sum_{k=1}^mx_k &\sum_{k=1}^mx_k^2 &\cdots ...
0
votes
1answer
52 views

Completeness of eigenvectors of Hermitian Matrix.

How do you show that eigenvectors of a Hermitian matrix form a complete set of basis?
1
vote
1answer
53 views

condition number after scaling matrix

Maybe a well-known question. Let $\Sigma$ represent a real symmetric positive definite matrix, i.e. a covariance matrix. Which diagonal matrix $D$ with positive diagonal minimizes the condition ...
0
votes
0answers
46 views

Least squares problem where rows are multiplied by a factor

I want to solve the following linear system in least squares sense: $Ax = b$ Where $A$ is a sparse matrix which has more rows than columns. To solve it in least squares sense I would need to solve ...
0
votes
1answer
25 views

Proving the equality: $D^{-1}+D^{-1}CPBD^{-1}=(D-CA^{-1}B)^{-1}$ where $P=(A-BD^{-1}C)^{-1}$

I am trying to prove the following equality that I need to use as an intermediate step to solve one of my problems. The equality is the following: $D^{-1}+D^{-1}CPBD^{-1}=(D-CA^{-1}B)^{-1}$, where ...
0
votes
1answer
64 views

Dense symmetric positive definite matrix

How could one define a dense symmetric positive definite matrix (dimension $1000 \times 1000$) with uniformly distributed eigenvalues (with the smallest eigenvalue $1$ and the condition number $100$) ...
2
votes
0answers
44 views

linear algebra formulation help

I asked this on mathoverflow as well and apologies for cross-posting. I am trying to compute this so-called bending energy matrix. The bending energy of a thin plate in 3D is given by: $$ BE = ...
2
votes
1answer
117 views

Help in this exercise about Richardson extrapolation.

We know $F(h)=a_0 +a_1h + a_2 h^3$ $F(1)=4$; $F(1/2)=21/8$; $F(1/4)=145/64$ Find a approximation of $F(0)=a_0$ with Richardson extrapolation method with an absolute error less than $10^{-2}.$ ...
0
votes
1answer
27 views

If $λ_i > 0, \forall i$, $A$ is positive definite

Given that $A \in R^{n,n}$, $λ_i $ the eigenvalues and $x_i$ the eigenvectors ($x_i^Tx_j=δ_{ij}$). I have to show that if $λ_i > 0, \forall i$, $A$ is positive definite. My idea is the following: ...
1
vote
0answers
66 views

Proof-finding: Power iteration and complexity of the Rayleigh quotient

I'm searching for a proof for this theorem: \begin{align} |\lambda^{(k)}-\lambda_1| = \mathcal{O}\Big(\Big|\frac{\lambda_2}{\lambda_1}\Big|^{2k}\Big) \end{align} where \begin{align} \lambda^{(k)} ...
4
votes
4answers
248 views

How to find 2x2 matrix with non zero elements and repeated eigenvalues?

I need to find a 2x2 matrix with non zero elements that has eigenvalue = 1 repeated (double). How can i do that? Thanks!
0
votes
0answers
26 views

Doubts on Conjugate and Biconjugate Gradient Method

I am not able to prove that $r^t_iAd_j=0$ for $j\neq i-1$, given $r^t_i$ the $i$-th residual $b-Ax_i$ and $d_j$ the $j$-th $A$-conjugate direction ...
1
vote
1answer
82 views

Computing the best-fit plane normal from n points

I've been working steadily through "3D Math Primer for Graphics and Game Development" and am stuck on how the authors derived their equation for the best-fit plane normal given n points. Please note, ...
3
votes
0answers
63 views

Difference between Householder Reflections and Gram-Schmidt?

In numerical QR decomposition, when we calculate the orthonormal factor Q of a matrix, what is the difference in results if we use Householder Reflections to normalize the matrix or use Gram-Schmidt ...
1
vote
2answers
41 views

Can you compute rank r factorization of a n*n matrix in time O(n^2 r)?

I am wondering if you can compute the SVD/eigenvectors of a rank r matrix of size n*n in time O(n^2 r)? My understanding is that standard eigenvector computations involve bringing matrix into ...
0
votes
0answers
66 views

Solve system of equations AXB = 0

Is there a common approach to solve a system of linear equations in a form $A^TXB = \bf{0}$? Where $A$ and $B$ are known matrices and $X$ is an unknown matrix. This seems simple enough, there should ...
0
votes
2answers
57 views

How to understand or show this?

We have $$F=ABh^{p_1}+\theta (h^{p_2})$$ $$G=Ah^{p_1}+\theta (h^{p_2})$$ We $A$,$B$ are real numbers, $h$ positive, $|h|\leq 1$ , $p_1<p_2$ natural numbers and $\theta(h)$ means that it is of ...
0
votes
1answer
53 views

Rate of Convergence of Generalized Iterative Method

Consider the generalized iterative method for finding polynomial roots: $z_{k+1}=z_k +d\frac{(1/p)^{(d-1)}(z_k)}{(1/p)^{(d)}(z_k)}$ where d is a positive integer. Note that Newton's Method is a ...
2
votes
3answers
91 views

properties of positive definite matrix

If $A$ is a symmetric positive definite matrix can we conclude $A^{n}$ is positive define too? Why? For example for $n=2$: $x^{T}(AA)x=x^{T}(AA^{T})x=(x^{T}A)^2>0$; for $n>2$?
0
votes
1answer
39 views

function of matrix and eigen values

I want to calculate exp(A), A is matrix, with numann series. is this series depend of matrix's eigen values? for example if it's eigen values are large, is numann series useful for this function?
0
votes
1answer
61 views

Differences between methods for solving linear equation system

I have a huge linear equation system in this form: F=K.Δ as usual form of problems in the finite element method, where the F vector and K are known and Δ vector is unknown. There are several ...
1
vote
1answer
157 views

Need matlab help to construct a numerical example for solving system of linear equation for random matrices

I am reading this paper(page 183). In this paper the iterative methods for computing some solution of the general restricted linear equations \begin{eqnarray} Ax = b, ~~~~ x\in R(A^{k})~~~~ b\in ...
1
vote
1answer
48 views

most efficient way to find distinct complimenting subspaces over a finite field

Let $V$ be a $n$-dimensional vector spaoce over $\mathbb{F}_p$ and let $W$ be a $k$-dimensional subspace. What's the most efficient way to algorithmically write down a basis for each distinct ...
3
votes
1answer
81 views

Understanding higher order SVD

Can someone explain the singular value decomposition of a tensor (maybe a 3 dimensional matrix) with an example? It is intuitively difficult to the get the meaning from just the formulas. On a ...
0
votes
2answers
51 views

A linear programming to obtain “canonical basis of convex cone”

In my research a I need to solve the linear equation (getting its null space) under some constraints. The matrix is given below: The constraints shall be (x1...x[16]>0, x[17]...x[20] arbitary...) ...
1
vote
1answer
52 views

Proof involving Gauss–Seidel method.

I've got a symmetric positive definite matrix $A$ that I decompose into $A=U+R$ where $U$ is the upper triangular portion of $A$ including the diagonal and $R$ is $A-U$. I've shown that $$x^TAx = ...
-1
votes
1answer
34 views

Find the equation to movement with a middle point locked

I have this scenario: One particle has to go from $0$ point to $y$ point in $1$ sec. The particle needs to start moving at time $0$ ($time=0sec$), and to go accelerating until the middle of time ...
1
vote
1answer
71 views

a conjugate gradients result for eigenvalue estimates

Consider the not preconditioned CG-method for a linear system $Ax=b$. Define $\beta_j = \frac{(r_{j+1},r_{j+1})}{(r_j,r_j)}$ and $\alpha_j=\frac{(r_j,r_j)}{(Ap_j,p_j)}$, where $(x,y) = y^Tx$ denotes ...
0
votes
1answer
28 views

Conditioning considerations in least square solutions via the normal equations

I'm a little unsure about how to classify conditioning issues with solving least squares equations via the normal equations approach. I'm hoping to get verification that what I say below is correct, ...
0
votes
0answers
53 views

Cholesky decomposition using Newton-Raphson

Hi I'm trying to do an alternative algorithm for the Cholesky factorization, which factorizes a symmetric pos. def. matrix $A=R^TR$ where $R$ is upper triangular. I'm curious what happens if you solve ...
3
votes
1answer
54 views

Solve Ax = b, but I have a function that implements A

I have an overdetermined linear system $Ax = b$. I need to choose an $x$. $x$ has about 100 elements in it. If I had the matrix $A$, I would set x equal $A^\dagger b$, the pseudoinverse of $A$ ...
1
vote
1answer
186 views

cube root of positive definite matrix

Suppose that $A$ is a real symmetric positive definite $20\times 20$ matrix with condition number $\kappa\le 1000$. I want to solve the system of linear equations $$A^{1/3}x=b$$ with $10$-digit ...
1
vote
0answers
59 views

Solving for A in the system Ax = 0

Consider the system of linear equations $A x = 0$ where $A$ is a $K \times M$ matrix of reals and $x$ is an $M \times 1$ vector of reals. The matrix $A$ is unknown but we can generate $x$s that ...
0
votes
0answers
26 views

only calculate diagonal of cholesky decomposition

I have a massive matrix $A$ that I can't hold entirely in memory, but it is possible to easily calculate individual entries ($A(i,j)$). I'm only interested in calculating the diagonal entries of the ...